[BOJ] 16235 나무재테크 - Java

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

16235번: 나무 재테크

[풀이]

문제에 적혀있는대로 구현하면 되는 문제였다.

* 봄 - 어린애부터 나이만큼 양분 먹고, 양분 못 먹는애는 여름에 죽이기

* 여름 - 봄에 양분 못 먹는애 죽이기

* 가을 - 나이가 5배수인 나무 8방으로 나이 1인 애 생성

* 겨울 - 땅에 양분 추가 A[][] 만큼

** 주의 - 봄에 양분 못 먹는애를 바로 죽이면 안되고, 봄애 모든 애들 다 체크하고 죽일애들 모아놓고 여름에 한 번에 죽여야한다. (바로 죽이면 양분되면서 더해진 양분으로 원래 죽어야 할 애가 양분 먹을 수 있다고 체크될 수 있음)

** 문제에서 심는 나무 위치를 x,y로 줘서 순서대로 col,row개념으로 생각한 나는 그렇게 했는데 아니었다. 그냥 x를 row, y를 col로 생각해야 하는듯 (개인적으로는 이거에 대한 설명이 더 필요하거나 용어가 바뀌어야 한다고 생각한다.)

 

 

[자료구조]

* 각 칸에 있는 나무들은 ArrayList<Integer>[][] MapTree 로 구성했다.

(= MapTree[i][j] 칸에 나무들 나이가 들어있는 ArrayList<Integer>가 존재하는 것임)

    -> 어린 나무부터 양분을 먹는다는 조건을 보고 PriorityQueue를 사용하면 되겠다고 생각했는데, iterate하는 과정에서 poll하고 add하면 순서가 꼬일 것 같아 그냥 ArrayList를 sorting 한 후 remove, add하는 방식을 사용했다.

    =>  근데 생각해보니 그냥 PriorityQueue쓰고, 새로운 PriorityQueue에 add 해서 그걸로 바꿔주면 되는 부분이었음

 

* ArrayList를 remove하는 방식에서 iterate시 주의할 것

하나의 Arr에서 원소를 remove하는 액션에서 주의해야할 것은 Arr의 구성이 변한다는 것이다.

ex) 처음 Arr에 [0,1,2,3,4] 5개의 수가 들어있다고 해보자. 각각의 인덱스는 0,1,2,3,4이다.

이 Arr를 index 0번부터 4번까지 remove하면서 동작을 수행하려고 했을 때, 

-> 처음 0번을 remove하면 Arr는 [1,2,3,4]가 된다. 그럼 각각의 인덱스는 0,1,2,3으로 변할 것이다.

-> 다음 인덱스 1번을 remove하려고 할 때 현재 Arr에서 index가 1번인 2을 remove하고 Arr는 [1,3,4] 가 된다.

원래 우리는 1을 remove하려고 했지만 Arr의 앞 구성이 바뀜으로 인해 index가 꼬인 경우다.

 

그렇다면, 어떻게 해주면 될까? => index를 역순으로 다뤄보자!

어차피 [0,1,2,3,4] 원소를 한 번씩 훑으면서 interate하는 것이 목적이니 한 번씩 훑기만 하면 된다.

그러므로 Arr를 index 4번부터 0번까지 역순으로 돌아가며 remove한다.

-> 처음 4번을 remove하면 Arr는 [0,1,2,3] 이 된다. 각각 인덱스는 그대로 0,1,2,3이다.

-> 다음 3번을 remove하면 Arr는 [0,1,2] 가 된다. 인덱스는 여전히 그대로다.

 

이렇게 한다면 하나의 Arr에서 remove하는 iteration을 순서 꼬임 없이 수행할 수 있다.

    ArrayList<Integer> test = new ArrayList<>();
    for(int i=0;i<10;i++){
        test.add(i);
    }
    Collections.sort(test, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return Integer.compare(o2,o1);
        }
    });
    System.out.println("=="+test);
    for(int i=test.size()-1;i>=0;i--){
        test.remove(i);
        test.add(i+100);
        System.out.println(i+"->"+test);
    }

* PriorityQueue에서 poll,add하는 액션에서 iterate 시 주의할 점

PriorityQueue는 넣으면 알아서 정렬해주는 매우 편한 친구다. 하지만 iterate할 때 큐에 삽입,삭제 액션이 들어간다면 큐가 정렬되어 구성이 변해버리고 말 것이고, 내가 처음 원했던 인덱스대로 동작을 하지 않을 것이다.

그렇기 때문에 절대로 iterate에서는 삽입,삭제 액션을 수행하면 안된다.

 

그럼 어떻게 하냐? => 새로운 PriorityQueue를 만들어서 거기에 넣고, 덮어쓰기

PriorityQueue<Integer> original = new PriorityQueue<>();
for(int i=0;i<10;i++){
	original.add(i);
}

while(true){
    PriorityQueue<Integer> newpq = new PriorityQueue<>();
    for(int i=0;i<original.size();i++){
        int N = original.poll();
        N += 3; //대충 값 바꿔주는 연산
        //original.add(N); //XXXXXX안된다.
        newpq.add(N); //새로운 pq에 삽입
    }
    original = new PriorityQueue<>(newpq); //기존 pq에 덮어씌운다.
}

[코드]

import java.io.*;
import java.sql.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Boj16235_나무재테크 {
    static StringTokenizer st;
    static int N,M,K;
    static int[][] Food;
    static ArrayList<Integer>[][] MapTree;
    static int[][] treeToFood;
    static int[][] NowFood;
    static int[] dRow = {-1,1,0,0,-1,-1,1,1}; //상하좌우,왼상 오상 왼하 오하
    static int[] dCol = {0,0,-1,1,-1,1,-1,1};
    static int answer = 0;

    public static void main(String[] args) throws Exception{
        System.setIn(new FileInputStream("src/main/java/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        Food= new int[N+1][N+1];
        NowFood= new int[N+1][N+1];
        for(int i=1;i<N+1;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1;j<N+1;j++){
                Food[i][j] = Integer.parseInt(st.nextToken());
                NowFood[i][j] = 5;
            }
        }
        MapTree = new ArrayList[N+1][N+1];
        for(int i=1;i<N+1;i++){
            for(int j=1;j<N+1;j++){
                MapTree[i][j] = new ArrayList<>();
            }
        }

        for(int i=1;i<M+1;i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int age = Integer.parseInt(st.nextToken());
           MapTree[x][y].add(age);
        }

        //시작
        for(int k=0;k<K;k++){
            treeToFood= new int[N+1][N+1];
            //봄
            for(int i=1;i<N+1;i++){
                for(int j=1;j<N+1;j++){
                    Collections.sort(MapTree[i][j], new Comparator<Integer>() {
                        @Override
                        public int compare(Integer o1, Integer o2) {
                            return Integer.compare(o2,o1);
                        }
                    }); //인덱스 거꾸로 돌거니까 나이 어린애가 마지막에 가게 정렬
                    
                    for(int m=MapTree[i][j].size()-1;m>=0;m--){ //역으로 iterate
                        int age = MapTree[i][j].remove(m);
                        if(age<=NowFood[i][j]){ //양분을 먹을 수 있으면
                            NowFood[i][j] -= age;
                            MapTree[i][j].add(age+1); //나이 증가해서 더하기
                        }
                        else{
                            //죽이고, 양분 충전할 것 모으기
                            int food = age/2;
                            treeToFood[i][j] += food;
                        }
                    }
                }
            }
           // System.out.println("===봄 끝===");
            //printMap();
            //여름
            for(int i=1;i<N+1;i++){ 
                for(int j=1;j<N+1;j++){
                    NowFood[i][j] += treeToFood[i][j]; //죽이기
                }
            }
//            System.out.println("===여름 끝===");
//            printMap();
            //가을
            for(int i=1;i<N+1;i++){
                for(int j=1;j<N+1;j++){
                    for(int m=0;m<MapTree[i][j].size();m++){
                        int age = MapTree[i][j].get(m);
                        if(age%5==0){
                            //8방으로 나이 1인 나무 생성
                            for(int d=0;d<8;d++){
                                int newRow = i + dRow[d];
                                int newCol = j + dCol[d];
                                if(1<=newRow && newRow<N+1 && 1<=newCol && newCol<N+1){
                                    MapTree[newRow][newCol].add(1);
                                }
                            }
                        }
                    }
                }
            }
//            System.out.println("===가을 끝===");
//            printMap();
            //겨울
            for(int i=1;i<N+1;i++){
                for(int j=1;j<N+1;j++){
                    NowFood[i][j] += Food[i][j]; //땅에 양분 추가
                }
            }
//            System.out.println("===겨울 끝===");
//            printMap();
        }

        //정답내기
        for(int i=1;i<N+1;i++){
            for(int j=1;j<N+1;j++){
                answer += MapTree[i][j].size();
            }
        }
        System.out.println(answer);


    }
    static void printMap(){
        for(int i=1;i<N+1;i++){
            for(int j=1;j<N+1;j++){
                System.out.println("("+i+","+j+") 나무 나이 : "+MapTree[i][j] +" 남은양분 : "+NowFood[i][j]);
            }
        }
    }
}

[느낀점]

소요시간 : 1h 10min

복잡했지만 할만했던 문제였다. 여름에 한 번에 죽여야 하는 조건을 보고도 봄에 묶어서 바로 처리하려고 했던 나 자신 반성하자

문제에서 하라는대로!

+ 삽입,삭제 시 iterate를 어떻게 처리하면 좋을지에 대해 생각할 수 있었던 문제