<BOJ> 16235 자바 (나무 재테크)

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

Singapore

 

 

 

 

 

구현 문제를 구분하는 힘이 부족했다.

 

 

입력

1. N M K
2. N 개의 줄에 A 배열의 값 A[r][c]
3. M 개의 줄에 나무의 위치(y, x), 나무의 나이(age)

​

봄: 자기 나이만큼 양분을 먹음, 나이 1증가

. 여러 개의 나무가 있음? 어린 나무부터 양분 섭취, => PQ 사용

. 자신 나이보다 양분이 적음? 즉시 죽음

​

여름: 봄에 죽은 나무가 양분으로 변함 (나이/2)

​

가을: 나무가 번식, 번식하는 나무의 나이는 5의 배수, 인접 8칸에 나이 1의 나무가 생김

​

겨울: 로봇이 땅을 돌아다니면서 땅에 양분을 추가, A[r][c]의 양이고 입력으로 주어짐

​

문제를 제대로 읽지 않아서 많이 헤맸는데.. 초기 양분 값이 5라는 걸 읽지 못하고 테스트 입출력이 잘못된 게 아닌가 싶었었다.

 

​

​

​

1차 풀이) 바로 시간 초과가 났다.

package algorithms.src;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class b16235_나무재테크 {
    static int N, M, K;
    static boolean flag;
    // 상 상우 우 하우 하 하좌 좌 상좌
    static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
    static PriorityQueue<Tree> q = new PriorityQueue<>();

    static int[][] A, map;
    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];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = 5;
            }
        }

        A = new int[N][N];

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


        // 나무의 위치
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int age = Integer.parseInt(st.nextToken());

            q.add(new Tree(y-1, x-1, age, 0, true));
        }

        System.out.println(BFS());

    }


    private static int BFS() {

        while (!q.isEmpty()) {
            Tree tree = q.poll();

            int ty = tree.y;
            int tx = tree.x;
            int age = tree.age;
            boolean alive = tree.alive;
            int weather = tree.weather % 4;

            if(tree.weather == K *4) {
                return q.size() +1;
            }

            switch (weather) {
                case 0 : // in spring
                    flag = false;
                    if(map[ty][tx] >= age) {
                        map[ty][tx] -= age;
                        age+=1;
                    } else alive = false;

                    q.add(new Tree(ty, tx, age, tree.weather+1, alive));
                    break;

                case 1:  // in summer , if false? age /2 +
                    if(!alive) map[ty][tx] += age/2;
                    else q.add(new Tree(ty, tx, age, tree.weather+1, alive));
                    break;

                case 2: // fall , 나무 번식
                    if(age %5 == 0) {
                        for (int i = 0; i < 8; i++) {
                            int ny = ty + dy[i];
                            int nx = tx + dx[i];
                            if (ny < 0 || ny >=N || nx < 0 || nx >= N) continue;
                            q.add(new Tree(ny, nx, 1, tree.weather+1, true));
                        }
                    }
                    q.add(new Tree(ty, tx, age, tree.weather+1, alive));

                    break;

                case 3: // winter, 양분 채워넣기
                    if(!flag) {
                        for (int i = 0; i < N; i++) {
                            for (int j = 0; j < N; j++) {
                                map[i][j] += A[i][j];
                            }
                        }
                        flag = true;
                    }
                    q.add(new Tree(ty, tx, age, tree.weather+1, alive));

                    break;
            }
        }

    return -1;
    }


    private static class Tree implements Comparable<Tree> {
        int y;
        int x;
        int age;
        int weather;
        boolean alive;

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

        @Override
        public int compareTo(Tree o) {
            if(this.weather != o.weather) {   // 1. 계절순으로
                return Integer.compare(this.weather, o.weather);
//                return this.weather - o.weather;
            } else
                return Integer.compare(this.age, o.age);
//                return this.age - o.age;   // 어린 나무부터 먹이자.

        }
    }
}

​

[1차코드 리뷰 및 2차 풀이]

​

😭 문제점)

1. 너무 많은 큐 연산이 이뤄졌다. 각 계절마다 모든 나무를 PQ에 다시 추가하고 있었기 때문에 큐의 삽입/삭제 연산이 과도하게 많아졌다.
2. 1번 문제에 의해 하나의 큐를 통해 처리하다 보니 불필요하고 복잡한 로직이 많이 늘어났다. 구현 문제만 맞닥드리면 나타나는 문제인듯 하다. 특히 계절 순환을 위한 weather 값을 계속 추적하는 부분이 비효율적이었다.

​

​

👀 해결방안)

1. 효율적인 데이터 구조사용

- 봄/여름 통합, PQ를 효율적으로 사용, 각 계절별로 나무 리스트를 갱신하여 큐 연산 최소화

2. 로직 단순화

- 계절별로 메서드 분리, 불필요 연산 제거

3. 한번의 순회

- 각 계절을 처리할 때 나무 리스트를 한 번만 순회.

​

package algorithms.src;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class b16235_나무재테크 {
    static int N, M, K;
    static final int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1}; // 방향 벡터 (상, 상우, 우, 하우, 하, 하좌, 좌, 상좌)
    static final int[] dx = {0, 1, 1, 1, 0, -1, -1, -1}; // 방향 벡터 (상, 상우, 우, 하우, 하, 하좌, 좌, 상좌)
    static PriorityQueue<Tree> treeQueue = new PriorityQueue<>(); // 나무들을 관리하는 우선순위 큐 (나이가 어린 나무부터)
    static int[][] nutrients, addNutrients; // 현재 양분과 겨울에 추가될 양분 배열

    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());

        nutrients = new int[N][N];
        addNutrients = new int[N][N];

        // 초기 양분 설정: 모든 칸에 5만큼의 양분이 있습니다.
        for (int i = 0; i < N; i++) {
            Arrays.fill(nutrients[i], 5);
        }

        // 겨울에 추가될 양분을 입력받습니다.
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                addNutrients[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 나무의 초기 상태를 입력받아 우선순위 큐에 추가합니다.
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken()) - 1;
            int x = Integer.parseInt(st.nextToken()) - 1;
            int age = Integer.parseInt(st.nextToken());
            treeQueue.add(new Tree(y, x, age));
        }

        // K년 후 살아남은 나무의 수를 출력합니다.
        System.out.println(simulateSeasons());
    }

    // K년 동안의 계절 순환을 시뮬레이션합니다.
    private static int simulateSeasons() {
        for (int year = 0; year < K; year++) {
            springAndSummer(); // 봄과 여름을 처리합니다.
            fall();            // 가을을 처리합니다.
            winter();          // 겨울을 처리합니다.
        }
        return treeQueue.size(); // 살아남은 나무의 수를 반환합니다.
    }

    // 봄과 여름을 처리하는 메서드
    private static void springAndSummer() {
        PriorityQueue<Tree> nextQueue = new PriorityQueue<>();
        List<Tree> deadTrees = new ArrayList<>();

        // 봄: 나무가 자신의 나이만큼 양분을 먹고 나이가 1 증가합니다.
        while (!treeQueue.isEmpty()) {
            Tree tree = treeQueue.poll();
            if (nutrients[tree.y][tree.x] >= tree.age) {
                nutrients[tree.y][tree.x] -= tree.age;
                tree.age++;
                nextQueue.add(tree);
            } else {
                deadTrees.add(tree);
            }
        }

        // 여름: 봄에 죽은 나무가 양분으로 변합니다.
        for (Tree deadTree : deadTrees) {
            nutrients[deadTree.y][deadTree.x] += deadTree.age / 2;
        }

        treeQueue = nextQueue; // 다음 계절을 위한 나무 리스트 갱신
    }

    // 가을을 처리하는 메서드: 나무가 번식합니다.
    private static void fall() {
        List<Tree> newTrees = new ArrayList<>();

        // 나이가 5의 배수인 나무가 인접한 8개의 칸에 나이가 1인 나무를 번식시킵니다.
        for (Tree tree : treeQueue) {    // poll을 하는 것이 아니라 단순 접근만 하는 것!
            if (tree.age % 5 == 0) {
                for (int i = 0; i < 8; i++) {
                    int ny = tree.y + dy[i];
                    int nx = tree.x + dx[i];
                    if (ny >= 0 && ny < N && nx >= 0 && nx < N) {
                        newTrees.add(new Tree(ny, nx, 1));
                    }
                }
            }
        }

        treeQueue.addAll(newTrees); // 새로운 나무를 기존 나무 리스트에 추가
    }

    // 겨울을 처리하는 메서드: 양분을 추가합니다.
    private static void winter() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                nutrients[i][j] += addNutrients[i][j];
            }
        }
    }

    // 나무 객체를 정의하는 클래스
    private static class Tree implements Comparable<Tree> {
        int y, x, age;

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

        // 나이가 어린 순으로 정렬하기 위해 compareTo 메서드 구현
        @Override
        public int compareTo(Tree other) {
            return Integer.compare(this.age, other.age);
        }
    }
}

​