나무 박멸 [2022-상반기 오후 2번 문제]
문제 링크
삼성 코딩테스트 기출 문제: 나무박멸 - 코드트리
주요 IT 기업의 코딩테스트 기출 문제를 연습하며 실전 감각을 키우세요. 취업 합격률을 높이는 필수 연습 과정입니다.
문제 설명
n*n 격자에 나무 그루 수와 벽의 정보가 주어짐. 제초제는 k의 범위 만큼 대각선으로 퍼지고, 벽이 있는 경우 가로막혀서 전파되지 않음.
- 인접한 4개의 칸 중 나무가 있는 칸의 수만큼 나무가 성장함. 성장은 모든 나무에게 동시에 일어남.
- 기존에 있었던 나무들은 인접한 4개의 칸 중 벽, 다른 나무, 제초제가 모두 없는 칸에 번식을 진행함. 총 번식이 가능한 칸의 개수만큼 나누어진 그루 수 만큼 번식이 되며, 나머지는 버림. 번식은 모든 나무에게 동시에 일어남.
- 각 칸 중 제초제를 뿌렸을 때 나무가 가장 많이 박멸되는 칸에 제초제를 뿌림. 나무가 없는 칸에 제초제를 뿌리면 박멸되는 나무가 전혀 없는 상태로 끝이 나지만, 나무가 있는 칸에 제초제를 뿌리면 4개의 대각선 방향으로 k칸 만큼 전파됨. 벽이 있거나, 나무가 아예 없는 칸의 경우 그 칸까지 뿌려지고 그 이후로는 전파되지 않음. 제초제는 c+1년이 될 때 사라짐.
해결 방법
- 제초제 시간 단축
제일 많이 제거되는 곳에 제초제를 뿌림
void spread_medi() {
int x, y;
int val = 0;
x = -1, y = -1;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (tmp_arr[i][j] > val) {
val = tmp_arr[i][j];
x = i, y = j;
}
}
}
result += val;
int nx, ny;
for (int d = 0;d < 4;d++) {
for (int i = 1;i <= k;i++) {
nx = x + dtx[d] * i, ny = y + dty[d] * i;
if (nx < 0 || ny < 0 || nx >= n || ny >= n) break;
medi[nx][ny] = c+1;
if (arr[nx][ny] <= 0) break;
if (arr[nx][ny] != -1) arr[nx][ny] = 0;
}
}
medi[x][y] = c+1;
arr[x][y] = 0;
}
각 나무 위치당 제초제를 뿌리면 제거할 수 있는 나무들을 tmp_arr에 기록
int get_medi(int x, int y) {
int nx, ny;
int ret = arr[x][y];
for (int d = 0;d < 4;d++) {
for (int i = 1;i <= k;i++) {
nx = x + dtx[d] * i, ny = y + dty[d] * i;
if (nx < 0 || ny < 0 || nx >= n || ny >= n) break;
if (arr[nx][ny] <= 0) break;
ret += arr[nx][ny];
}
}
return ret;
}
void use_medi() {
memset(tmp_arr, 0, sizeof(tmp_arr));
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (arr[i][j] <= 0) continue;
tmp_arr[i][j] = get_medi(i,j);
}
}
}
나무 번식
void tree_fert() {
memset(tmp_arr, 0, sizeof(tmp_arr));
int nx, ny;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (arr[i][j] <= 0) continue;
int cnt = 0;
for (int d = 0;d < 4;d++) {
nx = i + dx[d], ny = j + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (arr[nx][ny] == 0 && medi[nx][ny] == 0) cnt++;
}
for (int d = 0;d < 4;d++) {
nx = i + dx[d], ny = j + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (arr[nx][ny] == 0 && medi[nx][ny] == 0) {
tmp_arr[nx][ny] += (arr[i][j] / cnt);
}
}
}
}
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
arr[i][j] += tmp_arr[i][j];
}
}
}
나무 성장
void tree_grow() {
int nx, ny;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (arr[i][j] <= 0) continue;
int cnt = 0;
for (int d = 0;d < 4;d++) {
nx = i + dx[d], ny = j + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (arr[nx][ny] > 0) cnt++;
}
arr[i][j] += cnt;
}
}
}
void medi_time() {
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (medi[i][j] > 0) medi[i][j]--;
}
}
}
전체 코드
#include <iostream>
#include <cstring>
using namespace std;
int n, m, k, c;
int arr[21][21];
int medi[21][21];
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };
int result = 0;
void input() {
cin >> n >> m >> k >> c;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
cin >> arr[i][j];
}
}
}
void tree_grow() {
int nx, ny;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (arr[i][j] <= 0) continue;
int cnt = 0;
for (int d = 0;d < 4;d++) {
nx = i + dx[d], ny = j + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (arr[nx][ny] > 0) cnt++;
}
arr[i][j] += cnt;
}
}
}
int tmp_arr[21][21];
void tree_fert() {
memset(tmp_arr, 0, sizeof(tmp_arr));
int nx, ny;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (arr[i][j] <= 0) continue;
int cnt = 0;
for (int d = 0;d < 4;d++) {
nx = i + dx[d], ny = j + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (arr[nx][ny] == 0 && medi[nx][ny] == 0) cnt++;
}
for (int d = 0;d < 4;d++) {
nx = i + dx[d], ny = j + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (arr[nx][ny] == 0 && medi[nx][ny] == 0) {
tmp_arr[nx][ny] += (arr[i][j] / cnt);
}
}
}
}
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
arr[i][j] += tmp_arr[i][j];
}
}
}
int dtx[4] = { -1,-1,1,1 };
int dty[4] = { -1,1,-1,1 };
int get_medi(int x, int y) {
int nx, ny;
int ret = arr[x][y];
for (int d = 0;d < 4;d++) {
for (int i = 1;i <= k;i++) {
nx = x + dtx[d] * i, ny = y + dty[d] * i;
if (nx < 0 || ny < 0 || nx >= n || ny >= n) break;
if (arr[nx][ny] <= 0) break;
ret += arr[nx][ny];
}
}
return ret;
}
void use_medi() {
memset(tmp_arr, 0, sizeof(tmp_arr));
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (arr[i][j] <= 0) continue;
tmp_arr[i][j] = get_medi(i,j);
}
}
}
void spread_medi() {
int x, y;
int val = 0;
x = -1, y = -1;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (tmp_arr[i][j] > val) {
val = tmp_arr[i][j];
x = i, y = j;
}
}
}
result += val;
int nx, ny;
for (int d = 0;d < 4;d++) {
for (int i = 1;i <= k;i++) {
nx = x + dtx[d] * i, ny = y + dty[d] * i;
if (nx < 0 || ny < 0 || nx >= n || ny >= n) break;
medi[nx][ny] = c+1;
if (arr[nx][ny] <= 0) break;
if (arr[nx][ny] != -1) arr[nx][ny] = 0;
}
}
medi[x][y] = c+1;
arr[x][y] = 0;
}
void medi_time() {
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (medi[i][j] > 0) medi[i][j]--;
}
}
}
void print_arr() {
cout << "print_arr:\\n";
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (medi[i][j] > 0) {
printf("%2d ", -medi[i][j]);
}
else if (arr[i][j] == -1) {
printf(" @ ");
}
else printf("%2d ", arr[i][j]);
}
cout << "\\n";
}
}
void solve(int t) {
tree_grow();
tree_fert();
use_medi();
spread_medi();
medi_time();
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("sample_input.txt", "r", stdin);
input();
for (int i = 0;i < m;i++) {
solve(i);
}
cout << result;
}