BOJ - 16235 나무 재태크

나무 재태크 : https://www.acmicpc.net/problem/16235

---

Problem

---

Solve

봄,여름,가을,겨울 순으로 필요한 값들을 갱신해주고 K만큼 반복하면 된다.

문제 풀이순서는 아래와 같다.

1. N*N의 2차원 배열 5의 값으로 초기화
2. 나무의 정보(x,y,나이)를 저장하는 인스턴스 큐 리스트(trees) 생성 후 나이 오름차순으로 정렬해준다.
   • 삭제와 삽입이 검색보다 빈번하므로 List보다 Queue를 선택했다.
   • Queue 자료구조 같은 경우 Queue자체로는 정렬 계산이 불가능하지만, List로 형변환을 시켜준다면 정렬이 가능하다.
3. K만큼 봄,여름,가을,겨울 순서대로 필요한 값들을 갱신해준다.
   • 봄 : trees의 나무 정보를 앞에서 부터 가져와 현재 영양분 - 현재 나무 나이가 0보다 작다면 죽은 나무 리스트에 저장하고 그렇지 않다면 trees에 현재 나무를 다시 넣어준다.
   • 여름 : 죽은 나무 리스트에 있는 tree들의 나이/2만큼 죽은 나무 좌표에 영양분을 갱신해준다.
   • 가을 : trees의 나무 중 나이가 5의 배수인 나무들과 인접한 8곳에 나이 1 나무를 Queue에 추가해주고 trees에 있는 나무의 나이순으로 정렬한다.
   • 겨울 : 문제에서 주어진 영양분 만큼 각 좌표에 추가해준다.
4. trees에 남아있는 나무의 개수를 반환한다.

---

Code

public class 나무재태크 {
	//기준좌표로부터 순서대로 왼쪽 위, 위, 오른쪽 위, 왼쪽, 오른쪽, 왼쪽 아래, 아래, 오른쪽 아래
	static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    //영양분 배열
	static int[][] soil;
    //겨울에 추가될 영양분
	static int[][] add;
    //살아있는 나무 리스트
	static Queue<Tree> trees;
    //영양분 배열의 크기
	static int N;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		soil = new int[N][N];
		add = new int[N][N];
		trees = new LinkedList<>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
            	//초기 영양분은 5
				soil[i][j] = 5;
                //각 좌표에 추가 영양분
				add[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			int z = Integer.parseInt(st.nextToken());
			trees.offer(new Tree(x, y, z));
		}

		//trees에 저장된 나무 나이의 오름차순으로 정렬
		Collections.sort((List<Tree>)trees);
		while (K-- > 0) {
        	//봄,여름
			springToSummer();
            //가을
			fall();
            //겨울
			winter();
		}

		//살아있는 나무의 개수
		bw.write(String.valueOf(trees.size()));
		bw.flush();
		bw.close();
	}

	static void springToSummer() {
    	//영양분을 먹지 못해 죽은 나무 리스트
		Queue<Tree> dieTrees = new LinkedList<>();

		int treeSize = trees.size();
		for (int i = 0; i < treeSize; i++) {
			Tree currentTree = trees.poll();
            //영양분을 먹지 못하는 나무
			if (soil[currentTree.x][currentTree.y] - currentTree.age < 0) {
            	//죽은 나무 리스트에 저장
				dieTrees.offer(currentTree);
			} else {
            	//영양분을 먹었다면 해당 나무 나이만큼 영양분을 빼고 해당 나무 나이를 추가하고 살아있는 나무 리스트에 다시 추가
				soil[currentTree.x][currentTree.y] -= currentTree.age;
				currentTree.age += 1;
				trees.offer(currentTree);
			}
		}

		//죽은나무는 해당 나무의 나이/2 만큼 영양분으로 갱신
		for (Tree dieTree : dieTrees) {
			soil[dieTree.x][dieTree.y] += dieTree.age / 2;
		}
	}

	static void fall() {
		int treesSize = trees.size();
		for (int i = 0; i < treesSize; i++) {
			Tree tree = trees.poll();
            //나무의 나이가 5의 배수이면 인접 8군데에 나이1인 나무 추가
			if (tree.age % 5 == 0) {
				for (int j = 0; j < 8; j++) {
					int nx = tree.x + dx[j];
					int ny = tree.y + dy[j];
					if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
						trees.offer(new Tree(nx, ny, 1));
					}
				}
			}
			trees.offer(tree);
		}

		//살아있는 나무 중 나이가 적은 나무부터 영양분을 얻어야하므로 나이 오름차순으로 정렬
		Collections.sort((List<Tree>)trees);
	}

	//영양분 추가
	static void winter() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				soil[i][j] += add[i][j];
			}
		}
	}

	static class Tree implements Comparable<Tree> {
		int y;
		int x;
		int age;

		public Tree(int x, int y, int age) {
			this.x = x;
			this.y = y;
			this.age = age;
		}

		@Override
		public int compareTo(Tree o) {
			return this.age - o.age;
		}
	}
}

---

Result

초기 영양분이 5인것을 읽지 못해서 문제 이해하는데 오래걸렸다.. 꼼꼼히 문제를 읽자!

---

Reference