[백준] 16235번 나무 재테크

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q10000/Q16235.java

상도가 나무 재테크를 한다. 봄 여름 가을 겨울에 각 각 일어나는 일이 다르다.
봄에는 나무가 땅의 양분을 자기 나이만큼 흡수한다. 같은 땅에서는 나이가 어린 나무부터 양분을
흡수한다. 이 때 자기 나이보다 땅에 양분이 없으면 그 나무는 즉사한다.
여름에는 봄에 즉사했던 나무들이 해당 나무의 나이/2 만큼 해당 좌표의 땅에 양분이 된다.
가을에는 나무의 나이가 5의 배수이면 주변 모든 좌표(8개)에 나이가 1인 나무를 퍼트린다.
겨울에는 로봇 S2D2가 땅을 돌아다니면서 입력으로 주어진 해당 땅의 양분을 공급한다.
위 같은 과정을 거치면 1년이 흐른다. K년이 흘렀을 때, 살아남은 나무의 개수를 출력하여라.

처음 생각

한 좌표에 여러개의 나무가 있을 수 있으므로, 이를 고려하기 위해서 다양한 방법을 사용할 수 있을 것이다. 배열로 만들어 볼까하다가 List가 문뜩 떠올라서 List로 구현하였다.

▶ List로 (x,y) 좌표에 대한 여러 나무의 정보가 들어있어야하므로, 3중 List를 아래와 같이 구현하였다.

▶ List안에 ArrayList(x좌표)가 있고 그 안에 ArrayList(y좌표)가 있으며 해당 칸에 들어가야하는 나무들의 정보를 가지고 있는 Pair 객체로 타입을 구현해주었다.

1	static List<ArrayList<ArrayList<Pair>>> list = new ArrayList<>();

▶ 위와 같이 구현해주었을 경우는 List를 미리 다 채워놓아야 한다. 아래의 방법으로 x와 y에 대한 ArrayList를 add 시켜 주었다. x에 대응하는 n개를 add 시켜준 뒤, 각 x에 대한 y 대응으로 n개를 add시켜 주었다.

        // n개의 arrayList 생성
        for(int i=0;i<n;i++) {
            list.add(new ArrayList<>());
            for(int j=0;j<n;j++)
                list.get(i).add(new ArrayList<>());
        }

다음 생각

좌표 (x,y)에 대한 나무들을 넣을 방법을 구현하였으므로, 봄부터 여름 가을 겨울 순으로 차례대로 구현을 하였다.

▶ 삼중 반복문을 돌면서 아래와 같이 List에서 x,y 값에 따른 나무들을 검사해 주었다.

list.get(i).get(j).get(k)

▶ 봄에는 해당 좌표의 양분을 가지고 해당 나무가 살아남을 수 있나를 검사한다. 나이가 어린 나무 부터 검사를 하기 때문에 한 번 나무가 죽으면 그 뒤의 나무도 모두 죽기 때문에 여름과 합쳐서 작성해도 무방할 것 같다. 작성은 나무가 죽을 경우 나무 상태인 v 값을 1에서 0으로 바꿔주었다.

▶ 여름에는 다시 반복문을 돌면서 나무들을 검사해 죽은 상태(0)일 경우 해당 나무의 나이/2 만 큼 해당 좌표에 양분으로 추가해주었다. 양분이 되면 해당 나무는 사라져야 하기 때문에 remove(k)를 통해 없애준 후, list의 index가 한 칸씩 땡겨져 왔을 것이므로 k--를 통해 해당 index를 재 검사하도록 하였다.

▶ 가을에는 다시 반복문을 돌면서 나무들의 나이를 검사해 %5가 0이라면 즉, 나이가 5의 배수라면 주변 모든좌표(8 방향)의 List에 나무를 추가해 주었다. 이 때, 나무의 나이는 1이므로 add(0,나무)로 0번 index에 추가시켜 주었다. 봄에 어린 나무 부터 검사를 해야하기 때문이다.

▶ 겨울에는 미리 입력 받아놓았던, 양분 배열을 사용하고 있는 배열에 더해주었다.

다다음 생각

문제를 잘 읽어야한다.

▶ 좌표의 입력으로 들어오는 수가 0부터 시작이 아닌 1부터 시작이기 때문에 -1 처리를 해주었다.

▶ 입력으로 들어오는 양분 표는 겨울에 로봇 S2D2가 뿌리는 양분이지 처음 모든 땅의 양분은 5이다.

다다다음 생각

뒷 번호의 테스트 케이스가 틀리게 나와서 보니 가을에 8방향으로 나무들을 퍼트릴 때, 반복문 안에서 좌표 변환을 위해 사용하고 있는 변수인 z가 아닌 i를 적어놓아서 조금만 뿌려져서 잘 못 된 값이 나왔었다.

▶ 반복문 사용할 때 잘 적어야 겠다.

방안

1) 항상 변수 이름 확인 잘하기.

package baekjoon.q10000;
 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Q16235 {
    static int n,m,k;
    static int[][] arr,copy;
    static List<ArrayList<ArrayList<Pair>>> list = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // n*n 배열
        m = sc.nextInt(); // 나무 정보 수
        k = sc.nextInt(); // K년이 지난후.
        
        arr = new int[n][n];
        copy = new int[n][n]; // 추가 되어야할 양분
        // n개의 arrayList 생성
        for(int i=0;i<n;i++) {
            list.add(new ArrayList<>());
            for(int j=0;j<n;j++)
                list.get(i).add(new ArrayList<>());
        }
        // 초기 양분값
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                copy[i][j] = sc.nextInt();
                arr[i][j] = 5; // 초기 양분은 5
            }
        }
        // m개의 줄에 상도가 심은 나무정보수 (x,y), 나무나이
        for(int i=0;i<m;i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int age = sc.nextInt();
            list.get(x-1).get(y-1).add(new Pair(x-1, y-1, 1, age));
        }
        
        // K년 동안
        for(int i=0;i<k;i++) {
            // 1년은 4계절
            solveSpring();
            solveSummer();
            solveFall();
            solveWinter();
        }
        // k년이 흐른 후 살아있는 나무 조사
        int result = 0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                result += list.get(i).get(j).size();
            }
        }
        System.out.println(result);
    }
    // 겨울에는 땅에 양분을 추가한다. 각 칸에 추가되는 양분은 초기 입력 양분이다.
    private static void solveWinter() {
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                arr[i][j] += copy[i][j];
            }
        }
    }
    // 가을에는 나무가 번식한다. 나이가 5의 배수인 나무의
    // 인접 8칸에 나이가 1인 나무가 생긴다.
    static int[][] dir = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    private static void solveFall() {
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                    for(int k=0;k<list.get(i).get(j).size();k++) {
                        // age가 5의 배수가 아니라면 패스
                        if(list.get(i).get(j).get(k).age%5!=0) continue;
                        for(int z=0;z<8;z++) {
                            int tx = i+dir[z][0];
                            int ty = j+dir[z][1];
                            if(tx<0 || ty<0 || tx>=n || ty>=n) continue;
                            // 해당 칸이 나이가 1인 나무 생성
                            list.get(tx).get(ty).add(0,new Pair(tx, ty, 1, 1));
                        }
                    }
            }
        }
    }
    // 여름에는 봄에 죽은 나무가 양분으로 변한다.
    // 죽은 나무의 나이/2가 양분으로 해당칸에 추가된다.
    private static void solveSummer() {
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                    // 해당 좌표의 나무들을 보면서 0인것을 없애주자.
                    for(int k=0;k<list.get(i).get(j).size();k++) {
                        // 죽은 나무라면
                        if(list.get(i).get(j).get(k).v==0) {
                            arr[i][j] += list.get(i).get(j).get(k).age/2;
                            // k--를 해주어 없어진 걸로 인한 영향을 없앤다.
                            list.get(i).get(j).remove(k);
                            k--;
                        }
                }
            }
        }
    }
    
    // 봄에는 나무가 나이만 큼 양분을 먹고 나이가 +1 (자신칸만 가능)
    // 하나의 칸에 여러 개의 나무가 있따면 나이 어린 나무가 먼저 먹는다.
    // 양분이 부족해 먹지못하면 먹지 않고 바로 즉사
    private static void solveSpring() {
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                // 나무 검사
                for(int k=0;k<list.get(i).get(j).size();k++) {
                    if(list.get(i).get(j).get(k).age>arr[i][j]) {
                        // 나무의 나이가 더 크다면 즉사
                        list.get(i).get(j).get(k).v = 0;
                    }else {
                        // 해당지역 나이 만큼 양분 감소
                        arr[i][j] -= list.get(i).get(j).get(k).age++;
                    }
                }
            }
        }
    }
    
    static class Pair{
        int x,y; // 위치
        int v; // 상태 (1살음,0죽음)
        int age; // 나이
        Pair(int x,int y,int v,int age){
            this.x = x;
            this.y = y;
            this.v = v;
            this.age = age;
        }
    }
}