[Java] 백준 16235번 나무 재테크

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

16235번: 나무 재테크

문제

---

코드 리뷰

---

이번 문제는 시뮬레이션입니다.

저는 문제를 읽고 생각보다 그냥 조건이 많고 쉽다라고 생각했습니다.

실제로도 문제 자체는 쉬웠습니다.

하지만 저는 이문제에만 3시간 가까이 사용해버렸죠....

계속 마지막 예제가 53이 나오는 겁니다.

그 이유가 나무를 저장하는 queue가 저장되는 값이 계속 바뀌는데 queue.size()로 for문을 돌려버리니 값이 제대로 나오지 않는 것이었습니다.

이 문제를 찾는다고 2시간 30분은 쓴것같습니다.

 

1. 봄
나무가 자신의 나이만큼 양분을 먹고 나이가 1 증가, 한칸에 여러 나무가 있을 경우 나이가 어린순, 나이보다 양분이 작을 경우 나무는 죽음
2. 여름
봄에 죽은 나무가 양분으로 변함, 죽은 나무 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가
3. 가을
나무가 번식, 번식하는 나무는 나이가 5의 배수, 인접한 8칸에 나이가 1인 나무가 생김
4, 겨울
양분 추가, 각 칸에 추가되는 양분의 양은 A[r][c]이다.

저는 4개의 조건을 생각하면서 풀었고 4가지 조건만 지킨다면 쉽게 풀린다고 생각합니다.

실수만 하지 않는다면....

 

 

package BJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_나무재테크 {
	static int N, M, K;
	static int map[][];
	static int add[][];
	static Queue<Tree> trees;
	static int[] dx = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int[] dy = { 0, -1, -1, -1, 0, 1, 1, 1 }; // 좌 좌상 상 우상 우 우하 하 좌하
	static int result;

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

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

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer 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];
		add = new int[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = 5;
				add[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		trees = new LinkedList<>();

		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 age = Integer.parseInt(st.nextToken());
			trees.add(new Tree(x, y, age));
		}
		
		Collections.sort((List<Tree>) trees); // 나이순으로 정렬

		System.out.println(finance());
	}

	private static int finance() {
		while(K-- > 0) {
			spring();
			fall();
			winter();
		}

		return trees.size();
	}

	private static void spring() {
		ArrayList<Tree> die = new ArrayList<>();
		
		int size = trees.size();
		for (int i = 0; i < size; i++) {
			Tree now = trees.poll();
			if (map[now.x][now.y] - now.age < 0) {
				die.add(new Tree(now.x, now.y, now.age / 2)); // 죽은 나무 리스트에 추가
			}else { // 양분이 나무의 나이보다 크거나 같을 경우
				map[now.x][now.y] -= now.age; // 양분을 나무의 나이만큼 빼줌
				trees.add(new Tree(now.x, now.y, now.age + 1));
			} 
		}
		for (Tree t : die) {
			map[t.x][t.y] += t.age; 
		}
	}

	private static void fall() {
		
		ArrayList<Tree> parents = new ArrayList<>();
		int size = trees.size();
		while (size-- > 0) {
			Tree now = trees.poll();
			if(now.age % 5 == 0) { // 나무의 나이가 5의 배수가 아닐 경우 번식 안함
				for (int j = 0; j < 8; j++) {
					int nx = now.x + dx[j];
					int ny = now.y + dy[j];
					
					if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue; // map의 크기를 벗어나면 번식 안함
					
					trees.add(new Tree(nx, ny, 1)); // 나무가 번식함
				}
			}
			parents.add(now);
		}
		
		for (Tree t : parents) {
			trees.add(t);
		}
	}

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

	}

}

 

Ysik Github : https://github.com/Y1sik/Algorithm/blob/main/BJ/BJ_%EB%82%98%EB%AC%B4%EC%9E%AC%ED%85%8C%ED%81%AC.java