[Baekjoon]16235.나무 재테크

16235. 나무 재테크

http://www.acmicpc.net/problem/16235

16235번: 나무 재테크

---

문제에 나와있는 봄, 여름, 가을, 겨울 순서대로 구현하면 되는 문제였다. 역시 특별한 알고리즘을 요구하지 않는 시뮬레이션 문제였다. 하지만 어떤 자료구조를 사용해서 풀 것인지를 빠른 시간안에 선택하는 것이 핵심인것 같다. 그리고 이 문제에서도 좌표를 반대로 생각해서 한동안 애를 먹었다. 좌표에 다시 한번 주의하자. 

 

처음에는 Tree클래스를 따로 만들어서 나무의 좌표와 나이를 저장하도록 한 다음 ArrayList에 나무들의 정보를 저장해서 풀어나가는 방식을 사용했다. 그런데 문제에서 한칸에 여러개의 나무가 있을 수 있다고 했는데 위와 같은 방법으로는 저 문제를 해결할 방법이 생각나지 않았다. 그래서 다른 사람의 풀이를 참고하여 2차원 리스트를 사용해서 풀었다.

 

나무의 정보를 담을 2차원 리스트 trees를  N x N ArrayList배열 로 생성하면 각 좌표마다 ArrayList를 가지므로 한 칸에 여러개의 나무가 들어가는 것을 구현할 수 있다. 각 ArrayList는 나무들의 나이 정보만 원소로 가진다. 

 

같은 칸에 여러 개의 나무가 있을때 어린 나무부터 양분을 먹어야 하므로 칸마다 나무의 나이를 오름차순으로 정렬한다. 이 때 Comparator로 정렬을 정의해줄 필요가 있다. 처음에 죽은 나무를 처리하기 위해 remove 메소드를 이용해 삭제했었는데 remove메소드를 사용하면 해당 인덱스 값이 지워지면 한 칸씩 밀려서 다른 원소로 채워지기 때문에 반복문 사용시에 모든 원소를 탐색하지 못하는 문제가 발생했다. 그래서 alive라는 리스트를 따로 만들어서 살아남은 나무들을 저장하고 반복문이 끝나면 해당 칸의 ArrayList를 alive로 갱신하도록 했다. 

private static void start() {
		
		int year = 0;

		while (true) {
			if (year == K) {
				return;
			}

			for (int i = 0; i < N; i++) { // 봄, 여름
				for (int j = 0; j < N; j++) {

					Collections.sort(trees[i][j], comparator);
					List alive = new ArrayList<>(); // 살아남은 나무 
					int dead = 0;

					for (int k = 0; k < trees[i][j].size(); k++) {

						int age = trees[i][j].get(k);

						if (map[i][j] < age) { // 양분이 모자라면
							dead += (age / 2);
						} else { 		       // 양분이 충분하면
							map[i][j] -= age;
							alive.add(age + 1);
						}
					}
					
					map[i][j] += dead;
					trees[i][j] = alive;
					
				}
			}

			for (int i = 0; i < N; i++) { // 가을
				for (int j = 0; j < N; j++) {
					
					for (int k = 0; k < trees[i][j].size(); k++) {
						
						int age = trees[i][j].get(k);
						
						if (age % 5 == 0) {
							for (int l = 0; l < 8; l++) {
								int tx = j + dx[l];
								int ty = i + dy[l];

								if (tx >= 0 && ty >= 0 && tx < N && ty < N) {
									trees[ty][tx].add(1);
								}
							}
						}
					}
					
				}
			}

			for (int i = 0; i < N; i++) { // 겨울
				for (int j = 0; j < N; j++) {
					map[i][j] += nut[i][j];
				}
			}

			year++;
		}
	}

<전체코드>