백준 16235 - 나무 재테크
Updated:
Java
16235 번 - 나무 재테크
문제
- 처음에 모든 칸에 양분 5
- M개의 나무를 심는다
- 한 칸에 여러개의 나무를 심을 수 있다.
- 봄 : 각각의 칸 마다 어린 나무 부터 나이만큼 양분을 섭취, 나이 증가한다. 만약 양분 섭취 x일시 죽음
- 여름 : 죽은 나무, 나이 / 2 만큼 양분추가
- 가을 : 5의 배수인 나무는 8방향으로 씨를 퍼뜨림
- 겨울 : 입력으로 주어진 A[][] 만큼 양분 추가
접근 방법
구현 및 시뮬레이션 문제였기 때문에, 처음 구현은 쉽게 하였다.
총 2번의 시간초과 후 성공하였는데,
-
첫번 째 시도
처음 접근 할 때, 각 칸마다 PriorityQueue를 사용하여 나무를 나이 순으로 정렬하여 매번 앞에서 부터 확인하도록 하였다.
이는 매번 나무의 나이를 정렬하는 꼴이 되므로, 시간초과를 초래하였다.
따라서, 입력으로 주어지는 나무의 위치는 모두 서로 다르다는 것과, 나이든 나무는 항상 제일 앞에 있게 된다는 것을 이용하여 Deque을 사용하였다.
Deque을 사용하여, 제일 뒤 즉 제일 최근에 추가된 나무의 나이가 제일 어리다는 것을 이용하여 뒤에서 부터 하나씩 pollLast하여 확인하는 방식으로 바꾸었다. -
두번째 시도
하지만, 여전히 시간 초과를 초래하였다.
나의 코드를 다시 확인하니,가을연산을 할 때, 매번 모든 나무를 poll하고 5의 배수를 찾은 뒤 다시 add를 하는 번거로운 작업을 거치고 있었다.
이는 2배의 연산을 하게 되는 것이므로, 봄에서 나이가 먹은 나무가 5의 배수가 될 때마다, 그 위치에 개수를 체크하여, 나중에 가을에 그 개수 만큼만 주위에 퍼뜨리도록 하였다.
따라서 세번 째 시도에서 성공하였다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, m, k, result;
static int[][] A; // 겨울마다 채워지는 양분의 양
static int[][] farm; // 현재 땅의 양분 상태
static int[][] dead; // 죽은 나무로 얻는 양분
static int[][] isSpread; // 퍼뜨릴 나무의 위치
static List<List<Deque<Integer>>> tree; // n x n의 각 칸의 나무들
static Stack<Integer> temp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
n = stoi(stk.nextToken());
m = stoi(stk.nextToken());
k = stoi(stk.nextToken());
A = new int[n][n];
farm = new int[n][n];
dead = new int[n][n];
isSpread = new int[n][n];
tree = new ArrayList<List<Deque<Integer>>>();
temp = new Stack<Integer>();
for(int i = 0; i < n; i++) {
stk = new StringTokenizer(br.readLine());
tree.add(new ArrayList<Deque<Integer>>());
for(int j = 0; j < n; j++) {
A[i][j] = stoi(stk.nextToken());
farm[i][j] = 5;
tree.get(i).add(new ArrayDeque<>());
}
}
int y,x,d;
while(m-- != 0) {
stk = new StringTokenizer(br.readLine());
y = stoi(stk.nextToken()) - 1;
x = stoi(stk.nextToken()) - 1;
d = stoi(stk.nextToken());
tree.get(y).get(x).add(d);
}
int[] dy = new int[] {-1,-1,-1,0,0,1,1,1};
int[] dx = new int[] {-1,0,1,-1,1,-1,0,1};
int age, ny, nx;
// 1년씩 지난다
while(k-- != 0) {
// 봄
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
// 뒤에서 부터 하나씩 poll 하여 나무의 나이를 증가시키고, 죽은 나무를 거른다.
while(!tree.get(i).get(j).isEmpty()) {
age = tree.get(i).get(j).pollLast();
// 나무 나이 만큼의 양분이 남아 있으면
if(age <= farm[i][j]) {
farm[i][j] -= age;
age++;
temp.add(age);
// 만약 나무의 나이가 5의 배수면, 가을에 퍼뜨리도록 체크한다.
if(age % 5 == 0) {
isSpread[i][j]++;
}
}
else {
// 죽은 나무의 최후
dead[i][j] += age / 2;
}
}
while(!temp.isEmpty()) {
tree.get(i).get(j).add(temp.pop());
}
}
}
// 여름
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
farm[i][j] += dead[i][j];
dead[i][j] = 0;
}
}
// 가을
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
while(isSpread[i][j] > 0) {
isSpread[i][j]--;
for(int p = 0; p < 8; p++) {
ny = i + dy[p];
nx = j + dx[p];
// 범위 내에 있으면 새로운 나무를 추가한다.
if(isIn(ny,nx)) {
tree.get(ny).get(nx).add(1);
}
}
}
}
}
// 겨울
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
farm[i][j] += A[i][j];
}
}
}
// 살아 남은 나무 수 구하기
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
while(!tree.get(i).get(j).isEmpty()) {
tree.get(i).get(j).poll();
result++;
}
}
}
System.out.println(result);
br.close();
}
// 주어진 범위 안에 있는가
public static boolean isIn(int y, int x){
if(y < 0 || y >= n || x < 0 || x >= n)
return false;
return true;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
후기
구현 하는데는 할 만 했던 문제지만, 시간 초과의 지옥에서 2번만에 탈출한 것에 감사한 문제이다.
