문제
입력
첫 번째 줄에 격자의 크기 n, 박멸이 진행되는 년 수 m, 제초제의 확산 범위 k, 제초제가 남아있는 년 수 c
이후 n개의 줄에 걸쳐 각 칸의 나무의 그루 수, 벽의 정보가 주어집니다.
총 나무의 그루 수는 1 이상 100 이하의 수로, 빈 칸은 0, 벽은 -1으로 주어지게 됩니다.
출력
m년 동안 총 박멸한 나무의 그루 수
풀이
제한조건
- 5 ≤ n ≤ 20
- 1 ≤ m ≤ 1000
- 1 ≤ k ≤ 20
- 1 ≤ c ≤ 10
접근방법
시뮬레이션
아주 전형적인 삼성 A형 스타일의 문제이다.
주어진 조건을 하나씩 만족하게 기능을 구현해서 조립하면 된다.
문제의 조건을 보며, 풀이과정을 그려보자.
1. 입력을 받는다.
2. 나무가 성장한다.
3. 나무가 번식한다.
4. 제초제를 뿌릴 위치를 선정한다.
5. 제초제를 뿌린다.문제는 길어보이지만 단순히 위의 5가지가 M년 동안 반복된다.
즉 아래와 같은 틀이 생긴다.
int count = 0;
for (int i = 0; i < M; ++i) {
// 성장, 번식
growth();
// 제초
count += killTree();
// 제초제 감소
decrease();
}
print(count)하나씩 항목을 살펴보자.
1. 입력을 받는다.
n, m, c, k와 격자의 내용을 적당한 배열에 담는것은 문제가 없다.
(입력으로 주어지기 때문)
이제 입력으로 주어지지는 않지만 문제에 필요한것이 어떤것이 있을지 생각해보자.
우선 제초제가 뿌려진 영역을 기록해둘 배열이 필요하다. (코드의 impossible)
또한 나무의 성장과정에서 모든 나무의 성장을 동시에 반영할 수 있도록 임시배열도 필요하다
(코드의 copy)
입력은 단순하기에 더 다룰 내용이 없다.
2. 나무가 성장한다. + 3. 나무가 번식한다.
2번과 3번은 함께 다루어보자. (이중 For문 하나로 해결하기 위함 + 하고자 하는 것이 비슷함)
나무의 성장은 인접한 나무의 수만큼 이루어진다.
이중 For문 내부에서 인접한 나무의 수만큼 현재 나무를 증가시킨다.
당연히 이중 For를 수행하며 (x,y)에 나무가 없거나, 벽이라면 continue로 넘겨주자.
나무의 번식 또한 성장과 유사한 코드의 반복이다.
다만, 번식 과정에서는 제초제가 뿌려진 영역에 나무가 번식할 수 없음을 유의한다.
아래와 같은 형식의 코드가 나올 것이다.
제초제가 뿌려질 때마다, impossible 배열의 해당 위치에 C+1을 할당했다.
매년 1씩 낮아지고, 0이면 제초제가 모두 소멸한 상태를 의미한다.
// 나무의 번식
int breeding = 0;
for (int d = 0; d < 4; ++d) {
int nx = i + gdx[d];
int ny = j + gdy[d];
if (!isInRange(nx, ny))
continue;
if (impossible[nx][ny] > 0)
continue;
if (map[nx][ny] != 0)
continue;
breeding++;
}
for (int d = 0; d < 4; ++d) {
int nx = i + gdx[d];
int ny = j + gdy[d];
if (!isInRange(nx, ny))
continue;
if (impossible[nx][ny] > 0)
continue;
if (map[nx][ny] != 0)
continue;
copy[nx][ny] += map[i][j] / breeding;
}
// 원래 있던 나무의 수도 추가한다.
copy[i][j] += map[i][j];4. 제초제를 뿌릴 위치를 선정한다. + 5. 제초제를 뿌린다.
이 또한 하고자 하는 행위가 비슷하니 하나로 묶어서 이해해보자.
여기서 까다로울만한 것은 대각선으로 특정 조건을 만족할때까지 뻗어나가며 카운팅을 하는 부분이다.
보통 이쯤되면 하는 생각이 이미 이중 For문 내부인데, 방향을 위한 For문, K번 뻗어가기 위한 For문.. depth가 깊어보이고 시간초과가 두려워질 수 있다.
하지만 방향과 K번 뻗어가기 위한 For문은 상수의 크기가 크지 않다.
또한 for와 if 문의 연속으로 depth가 깊어보이는 것도 어쩔 수 없다.
for문으로 조건을 주며 찾는것보자 재귀로 작성하는것이 더 직관적으로 보였다.
재귀를 통해 최대 K번까지 수행하며 벽 또는 나무가 없는 구역까지 뻗어가며 카운팅을 했다.
최대 위치를 찾고 해당 위치에서 다시 재귀로 뻗어나가며
- 나무를 모두 제거.
- 제거된 위치에 제초제 살포
2가지 작업을 해준다.
이제 마지막으로 가장 잊기 쉬운 부분
매년 일련의 작업이 끝나면, 제초제의 수치를 감소시켜주자.
아래 코드에서는 이런 방식으로 제초제 부분을 구현했다.
제초제가 뿌려질 때마다, impossible 배열의 해당 위치에 C+1을 할당했다.
매년 1씩 낮아지고, 0이면 제초제가 모두 소멸한 상태를 의미한다.
다른 방식으로 구현했다면, 필요없는 부분이다.
(현재 a년 이고, 제초제가 b년까지 유효함 <-과 같은식의 구현에는 필요없음)
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int N, M, K, C;
static int[][] map, impossible;
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = in.readLine().split(" ");
N = stoi(inputs[0]);
M = stoi(inputs[1]);
K = stoi(inputs[2]);
C = stoi(inputs[3]);
map = new int[N][N];
impossible = new int[N][N];
for (int i = 0; i < N; ++i) {
inputs = in.readLine().split(" ");
for (int j = 0; j < N; ++j) {
map[i][j] = stoi(inputs[j]);
}
}
int count = 0;
for (int i = 0; i < M; ++i) {
// 성장, 번식
growth();
// 제초
count += killTree();
// 제초제 감소
decrease();
}
System.out.println(count);
}
static int[] dx = {-1, -1, 1, 1};
static int[] dy = {-1, 1, 1, -1};
public static int killTree() {
// 나무 선정
int max = 0;
int tx = 0;
int ty = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (map[i][j] < 1)
continue;
int count = map[i][j];
for (int d = 0; d < 4; ++d) {
count += findTree(i + dx[d], j + dy[d], d, 0);
}
if (count > max) {
max = count;
tx = i;
ty = j;
}
}
}
for (int d = 0; d < 4; ++d)
removeTree(tx + dx[d], ty + dy[d], d, 0);
map[tx][ty] = 0;
impossible[tx][ty] = C + 1;
return max;
}
public static void removeTree(int x, int y, int d, int depth) {
if (depth == K)
return;
if (!isInRange(x, y))
return;
impossible[x][y] = C + 1;
if (map[x][y] == 0 || map[x][y] == -1)
return;
map[x][y] = 0;
removeTree(x + dx[d], y + dy[d], d, depth + 1);
}
public static int findTree(int x, int y, int d, int depth) {
if (depth == K)
return 0;
if (!isInRange(x, y))
return 0;
if (map[x][y] == 0 || map[x][y] == -1)
return 0;
return map[x][y] + findTree(x + dx[d], y + dy[d], d, depth + 1);
}
public static void decrease() {
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
impossible[i][j]--;
}
static int gdx[] = {-1, 1, 0, 0};
static int gdy[] = {0, 0, -1, 1};
public static void growth() {
int[][] copy = new int[N][N];
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
// 나무가 없는 경우
if (map[i][j] == 0)
continue;
// 벽
if (map[i][j] == -1) {
copy[i][j] = -1;
continue;
}
if (impossible[i][j] > 0)
continue;
// 나무가 인접한 칸의 수를 확인한다.
int count = 0;
for (int d = 0; d < 4; ++d) {
int nx = i + gdx[d];
int ny = j + gdy[d];
if (!isInRange(nx, ny) || map[nx][ny] < 1)
continue;
count++;
}
map[i][j] += count;
// 나무의 번식
int breeding = 0;
for (int d = 0; d < 4; ++d) {
int nx = i + gdx[d];
int ny = j + gdy[d];
if (!isInRange(nx, ny))
continue;
if (impossible[nx][ny] > 0)
continue;
if (map[nx][ny] != 0)
continue;
breeding++;
}
for (int d = 0; d < 4; ++d) {
int nx = i + gdx[d];
int ny = j + gdy[d];
if (!isInRange(nx, ny))
continue;
if (impossible[nx][ny] > 0)
continue;
if (map[nx][ny] != 0)
continue;
copy[nx][ny] += map[i][j] / breeding;
}
// 원래 있던 나무의 수도 추가한다.
copy[i][j] += map[i][j];
}
}
int a = 1;
map = copy;
}
public static boolean isInRange(int x, int y) {
if (0 <= x && x < N && 0 <= y && y < N)
return true;
return false;
}
public static int stoi(String s) {
return Integer.parseInt(s);
}
}