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

📌문제 링크

---

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

📌문제 설명

---

구현 자체는 쉽지만, 시간초과를 해결하는것이 까다로운 문제입니다. 딕셔너리 / 해시맵을 사용해도 되고 필자는 priority queue를 이용해 문제를 해결했습니다. 좌표마다 priority queue를 두어 map과 비슷하게 구현을 하였습니다. 만약 정렬을 위해 queue에 모든 좌표의 나무를 넣으면 시간초과가 발생합니다.

📌코드

---

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader (System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static PriorityQueue<Integer>[][] trees; // 각 좌표에서 나무들의 나이를 관리하는 우선순위 큐 배열
    static int[][] mp, energe; // mp: 현재 땅의 양분, energe: 겨울에 추가될 양분
    static int[] dx = {1, 1, -1, -1, 0, 0, 1, -1}; // 8방향 이동을 위한 x 변화량
    static int[] dy = {1, -1, 1, -1, 1, -1, 0, 0}; // 8방향 이동을 위한 y 변화량
    static int N, M, K; // 격자의 크기 N, 초기 나무 수 M, 시뮬레이션 연도 K

    public static void main(String[] args) throws Exception {
        input(); // 입력 데이터를 읽어오는 메서드 호출
        solve(); // 문제 해결 로직 실행
    }

    // 입력 데이터를 처리하는 메서드
    static void input() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 격자 크기
        M = Integer.parseInt(st.nextToken()); // 초기 나무 수
        K = Integer.parseInt(st.nextToken()); // 시뮬레이션 연도

        mp = new int[N + 1][N + 1]; // 땅의 양분 배열
        energe = new int[N + 1][N + 1]; // 겨울에 추가될 양분 배열
        trees = new PriorityQueue[N + 1][N + 1]; // 나무의 나이를 관리할 우선순위 큐 배열

        // 배열 초기화
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                mp[i][j] = 5; // 초기 양분은 모두 5로 설정
                trees[i][j] = new PriorityQueue<>(); // 각 좌표에서 나무 나이를 관리할 우선순위 큐 초기화
            }
        }

        // 겨울에 추가될 양분 값 입력
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                energe[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 초기 나무 정보 입력
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()); // 나무의 x 좌표
            int y = Integer.parseInt(st.nextToken()); // 나무의 y 좌표
            int age = Integer.parseInt(st.nextToken()); // 나무의 나이
            trees[x][y].add(age); // 해당 좌표의 우선순위 큐에 나이 추가
        }
    }

    // 문제 해결 로직을 담고 있는 메서드
    static void solve() throws Exception {
        // K년 동안 시뮬레이션 실행
        for (int year = 0; year < K; year++) {
            springAndSummer(); // 봄과 여름 처리
            fall(); // 가을 처리
            winter(); // 겨울 처리
        }

        // K년 후 남아 있는 나무의 개수 계산
        int answer = countTrees();
        bw.write(answer + "\n"); // 결과 출력
        bw.flush(); // 출력 버퍼 비우기
        bw.close(); // 출력 스트림 닫기
    }

    // 봄과 여름을 처리하는 메서드
    static void springAndSummer() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (trees[i][j].isEmpty()) continue; // 해당 좌표에 나무가 없으면 건너뛰기
                PriorityQueue<Integer> newTrees = new PriorityQueue<>(); // 봄 이후의 나무를 저장할 큐
                int addedNutrients = 0; // 여름에 추가될 양분

                // 봄: 나무가 자신의 나이만큼 양분을 먹음
                while (!trees[i][j].isEmpty()) {
                    int age = trees[i][j].poll(); // 가장 어린 나무부터 처리
                    if (mp[i][j] >= age) {
                        mp[i][j] -= age; // 나무가 양분을 먹고
                        newTrees.add(age + 1); // 나이가 1 증가한 상태로 저장
                    } else {
                        addedNutrients += age / 2; // 양분 부족으로 죽은 나무의 나이 / 2만큼 양분으로 변환
                    }
                }

                // 여름: 죽은 나무가 양분으로 변환됨
                mp[i][j] += addedNutrients; // 죽은 나무에서 나온 양분 추가
                trees[i][j] = newTrees; // 나무 리스트 갱신
            }
        }
    }

    // 가을: 나무 번식 처리
    static void fall() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (trees[i][j].isEmpty()) continue; // 나무가 없는 좌표는 건너뛰기
                for (int age : trees[i][j]) {
                    if (age % 5 != 0) continue; // 나이가 5의 배수가 아닌 경우 번식하지 않음
                    for (int k = 0; k < 8; k++) {
                        int nx = i + dx[k]; // 번식할 새로운 x 좌표
                        int ny = j + dy[k]; // 번식할 새로운 y 좌표
                        if (nx < 1 || ny < 1 || nx > N || ny > N) continue; // 격자 범위를 벗어나면 무시
                        trees[nx][ny].add(1); // 새로 번식한 나무 추가 (나이는 항상 1)
                    }
                }
            }
        }
    }

    // 겨울: 양분 추가
    static void winter() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                mp[i][j] += energe[i][j]; // 겨울에 추가되는 양분만큼 더함
            }
        }
    }

    // 현재 모든 좌표에서 나무의 개수를 계산
    static int countTrees() {
        int count = 0; // 나무의 총 개수를 저장할 변수
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                count += trees[i][j].size(); // 각 좌표에서 나무의 개수를 더함
            }
        }
        return count; // 최종 나무 개수 반환
    }
}