문제
N x N 크기의 땅에 나무를 심고, 봄/여름/가을/겨울 4계절 과정을 K년 동안 시뮬레이션한 후 살아남은 나무의 수를 구하라.
입력
첫째 줄에 N (1 ≤ N ≤ 10), M (나무 수), K (년 수)가 주어진다. 이후 N줄에 겨울에 추가할 양분, M줄에 나무 정보(행, 열, 나이)가 주어진다.
출력
K년 후 살아남은 나무의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 1 1 1 1 1 1 | 1 |
풀이
4계절 과정을 Deque 자료구조로 관리하며 K년 반복 시뮬레이션한다.
- 초기 양분은 모든 칸에 5로 설정하고, 나무를 Deque에 저장한다
- 봄: 나이 어린 순으로 양분을 흡수(나이만큼 소모, 나이+1), 양분 부족 시 죽음 → 여름: 죽은 나무의 나이/2를 해당 칸 양분에 추가
- 가을: 나이가 5의 배수인 나무가 인접 8방향에 나이 1인 나무를 번식(addFirst로 앞에 삽입)
- 겨울: 입력받은 양분 배열만큼 모든 칸에 양분 추가
핵심 아이디어: Deque를 사용해 번식한 어린 나무를 앞에 삽입하면 별도 정렬 없이 나이 오름차순을 유지할 수 있다.
코드
package ASP_study.day299;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Day290BOJ16235나무재테크 {
static int[] dr = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int[] dc = { -1, 0, 1, -1, 1, -1, 0, 1 };
static int N, M, K;
static int[][] map;
static Deque<Tree> treeList;
static class Tree {
int row;
int col;
int age;
public Tree(int row, int col, int age) {
super();
this.row = row;
this.col = col;
this.age = age;
}
@Override
public String toString() {
return "Tree [row=" + row + ", col=" + col + ", age=" + age + "]";
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new int[N][N];
for (int i = 0; i < N; i++) {
Arrays.fill(map[i], 5);
}
Comparator<Tree> comparator = new Comparator<Tree>() {
@Override
public int compare(Tree A, Tree B) {
return A.age - B.age;
}
};
treeList = new LinkedList<>();
int[][] plusArr = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
plusArr[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int r = Integer.parseInt(st.nextToken()) - 1;
int c = Integer.parseInt(st.nextToken()) - 1;
int a = Integer.parseInt(st.nextToken());
treeList.add(new Tree(r, c, a));
}
for (int i = 1; i <= K; i++) {
spring(map);
autumn(map);
winter(map, plusArr);
}
System.out.println(treeList.size());
}
static void spring(int[][] map) {
Queue<Tree> dList = new LinkedList<>();
for (int i = 0; i < treeList.size();) {
Tree nowTree = treeList.poll();
if (map[nowTree.row][nowTree.col] >= nowTree.age) {
map[nowTree.row][nowTree.col] -= nowTree.age;
nowTree.age++;
i++;
treeList.add(nowTree);
} else {
dList.add(nowTree);
}
}
for (Tree t : dList) {
map[t.row][t.col] += t.age / 2;
}
}
static void autumn(int[][] map) {
Queue<Tree> templist = new LinkedList<>();
for (Tree t : treeList) {
if (t.age % 5 == 0) {
templist.add(t);
}
}
while (!templist.isEmpty()) {
Tree t = templist.poll();
for (int i = 0; i < 8; i++) {
int nr = t.row + dr[i];
int nc = t.col + dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= N)
continue;
treeList.addFirst(new Tree(nr, nc, 1));
}
}
}
static void winter(int[][] map, int[][] plusArr) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map[i][j] += plusArr[i][j];
}
}
}
static void print(int[][] map) {
for (int[] data : map) {
System.out.println(Arrays.toString(data));
}
}
}복잡도
- 시간: O(K * T * N²) (T: 나무 수, 최악의 경우 매년 전체 나무 순회)
- 공간: O(N² + T)