[백준 (Baekjoon)] (java) 문제 16235 - 구현

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

16235번: 나무 재테크

난이도

골드3

 

노트 (문제 읽으며 작성한 내용)

N*N의 땅: 정사각형
(r,c): 1로부터 시작함
초기 양분: 5
같은 위치 (r,c)에 1개 이상의 나무 존재 가능

-4계절-
<봄>
- 자신의 나이만큼 양분을 먹고 나이 1 증가
- 1개 이상의 나무 존재시 어린 순으로
- 나이 > 양분 --> 나무 즉시 죽음
<여름>
- 봄에 죽은 나무가 양분이 됨
- (r,c)의 양분 += 죽은나무의 나이/2
<가을>
- 번식, 나이가 5의 배수 이상인 나무 --> 인접한 8개 칸에 나이가 1인 나무 생김
<겨울>
- 땅에 양분 추가, 입력으로 주어진 A[r][c]만큼

K년이 지난 후 살아있는 나무의 개수

<입력>
N: 땅 크기
M: 나무 정보
x,y,z: 나무 위치 (x,y), 나이 z
K: 연도

<접근>
- 가장 어린 순으로 나이를 먹는다 --> PriorityQueue
--> 죽은 것들이 제일 앞에, 그 뒤로는 나이 어린 순으로
- N이 10이하이니 최대 100개의 PriorityQueue
--> 음.. 근데 가을에는 나이가 5의 배수 이상인거를.. 음.. 그럼 arraylist만들어서 봄에 나이가 5이상이 된 tree의 위치를 저장하자
- 봄/여름/가을/겨울로 method 나누기

접근

- 초기 작성한 노트와 달리 PriorityQueue대신 ArrayList를 사용하게 되었다

이유) 가장 어린 나무만 보는 것이 아닌, 해당 위치에 있는 모든 tree들을 순회해야하는데 PriorityQueue는 index 개념이 없어 순서대로 순회를 하는데는 적절치 않았다. 문제를 곰곰히 생각해보니 각 해마다 해당 위치의 모든 나무가 나이를 먹거나 죽기 때문에 중간에 순서가 반전될일은 없다. 따라서 처음 입력을 받을때만 tree들을 담은 ArrayList를 정렬해주었다.

- 4계절로 method를 나누지않고 year로 한번에 구현했다

이유) land로 땅의 양분을, trees로 각 땅에 위치한 나무들의 나이를 저장했을 때

• 봄: 해당 위치의 land와 trees를 확인 후 둘 다 update
• 여름: 해당 위치의 죽은 trees들을 이용해 land만 업데이트
• 가을: 나이가 5의 배수인 trees들을 이용해 land만 업데이트
• 겨울: 해당 위치의 A 값을 이용하여 land만 업데이트

라는 점을 깨달았다. 따라서 봄 이후의 계절에는 봄의 결과값또는 A만을 이용하지 각 process가 서로의 결과값을 참조하지는 않는다. 그렇기에 굳이 하나가 끝나고 그 다음을 진행하여 여러번 순환할 것이 아닌 한번의 이중 for-문을 이용한 순환으로 봄,여름,겨울을 해결하고 그 중에 나온 나이가 5의 배수인 tree들의 위치를 저장한 list를 이용해 한번에 번식(가을)을 진행하였다

코드

package implementation;

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

public class g3_16235 {
    static int N,M,K,count=0;
    static int[][] A, land;
    static List<Integer>[][] trees;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tok = new StringTokenizer(br.readLine());

        N = Integer.parseInt(tok.nextToken());
        M = Integer.parseInt(tok.nextToken());
        K = Integer.parseInt(tok.nextToken());

        A = new int[N][N];
        land = new int[N][N];
        trees = new ArrayList[N][N];

        for(int i=0;i<N;i++) {
            tok = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                A[i][j] = Integer.parseInt(tok.nextToken());
                land[i][j] = 5;
                trees[i][j] = new ArrayList<>();
            }
        }

        for(int i=0;i<M;i++) {
            tok = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(tok.nextToken())-1;
            int y = Integer.parseInt(tok.nextToken())-1;
            int z = Integer.parseInt(tok.nextToken());

            trees[x][y].add(z);

            if(trees[x][y].size()>1) Collections.sort(trees[x][y]);
        }

        count = M;

        for(int k=0;k<K;k++) {
            if(count==0) break;
            year();
        }

        System.out.println(count);
    }

    public static void year() {
        List<Location> procreate = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (trees[i][j].size() != 0) {

                    int deadAges = 0;

                    for (int a = 0; a < trees[i][j].size(); a++) {
                        int age = trees[i][j].get(a);
                        //봄
                        if (age <= land[i][j]) {
                            land[i][j] -= age;
                            age++;
                            if (age % 5 == 0) {
                                procreate.add(new Location(i, j)); //가을 준비
                            }
                            trees[i][j].set(a, age);
                        } else {
                            deadAges += age / 2; //여름 준비
                            trees[i][j].remove(a);
                            a--;
                            count--;
                        }
                    }

                    //여름
                    land[i][j] += deadAges;
                }
                //겨울
                land[i][j]+=A[i][j];
            }
        }

        //가을
        autumn(procreate);
    }

    public static void autumn(List<Location> procreate) {
        for(Location loc : procreate) {
            boolean canGoUp = loc.r>0;
            boolean canGoDown = loc.r<N-1;
            boolean canGoRight = loc.c<N-1;
            boolean canGoLeft = loc.c>0;

            if(canGoUp) {
                trees[loc.r-1][loc.c].add(0,1);
                count++;
                if(canGoLeft) {
                    trees[loc.r-1][loc.c-1].add(0,1);
                    count++;
                }
                if(canGoRight) {
                    trees[loc.r-1][loc.c+1].add(0,1);
                    count++;
                }
            }
            if(canGoDown) {
                trees[loc.r+1][loc.c].add(0,1);
                count++;
                if(canGoLeft) {
                    trees[loc.r+1][loc.c-1].add(0,1);
                    count++;
                }
                if(canGoRight) {
                    trees[loc.r+1][loc.c+1].add(0,1);
                    count++;
                }
            }
            if(canGoRight) {
                trees[loc.r][loc.c+1].add(0,1);
                count++;
            }
            if(canGoLeft) {
                trees[loc.r][loc.c-1].add(0,1);
                count++;
            }
        }
    }

}

class Location{
    int r;
    int c;

    public Location(int r, int c) {
        this.r = r;
        this.c = c;
    }
}