[백준 16235, Java] 나무 재테크

문제

www.acmicpc.net/problem/16235

16235번: 나무 재테크

 

풀이

 문제에서 주어진 봄 - 여름 - 가을 - 겨울 순서대로 조건과, 변화를 살펴보자

 

봄 : 나무가 양분을 먹는다

  양분을 먹는 양 : 나무의 나이만큼  

  양분을 먹는 칸 : 현재 나무의 위치 → 나무 클래스의 속성 : 나이, 위치(x,y)

  양분을 먹는 조건 :

   나이가 어린 나무 먼저 먹는다  → 무 클래스를 "나이" 순으로 정렬 할 수 있도록 Comparable구현, Collections.sort로 정렬필요

   양분이 부족할 경우 : 나무가 죽는다

 

여름 : 봄에 죽은 나무가 양분으로 된다

 양분으로 변하는 양 : 죽은 나무의 나이/2 → 죽은나무를 저장해야 하므로 봄에서   ArrayList에 죽은 나무를 저장한다

 

가을 : 나무 번식

 번식하는 나무 - 나무의 나이가 5의 배수인 나무

 번식 방향 : 상하좌우 대각선

 번식할 수 있는 곳 - map 안

 

겨울 : 양분 추가

 

처음에 생각하기 까다로웠던 부분은, "한칸에 여러나무가 있는 경우 나이가 어린 나무 먼저 양분을 먹는다"라는 조건이었다. 이걸 어떻게 구현해야할까 생각할때 ArrayList<Tree>[][] 를 생각했는데, 이건 디버깅도 어렵고 불필요한 메모리가 많다고 생각했다. "나이순"이라는 것을 힌트로 ArrayList<Tree>에 나이 순서대로 정렬을 하면 어짜피 나이가 가장 어린 나무먼저 양분을 먹게되니 굳이 map을 순서대로 순회할 필요가 없다고 생각했다.

 

실수한 부분

//봄 : 어린나무 먼저 양분을 먹는다
Collections.sort(trees);

ArrayList<Tree> deadTrees = new ArrayList<>();
ArrayList<Tree> liveTrees = new ArrayList<>();

for(int index =0; index<trees.size();index++){
	Tree currentTree = trees.get(index);
	int x = currentTree.x;
	int y = currentTree.y;
	int age = currentTree.age;

	if(age<=sugar[x][y]){
		//양분을 먹을 수 있다
		sugar[x][y] -= age;
		age +=1;
		liveTrees.add(new Tree(x,y,age));
	}
    else{
    //양분을 먹을 수 없다
    //deadTrees.add(trees.remove(index));
    deadTrees.add(new Tree(x,y,age));
    }
}

 

양분을 먹을 수 없다부분을 구현할 때 ArrayList에서 해당 나무를 삭제를 했는데, 이렇게 되면 for문으로 ArrayList를 순회시 끝까지 순회하지 못하게 된다. 중간에 사이즈가 변하기 때문이다. 따라서 이때 liveTrees를 선언하고서, 봄 이후에 trees에서 살아있는 나무들과 죽은나무들 두개로 나누었다. 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Tree implements Comparable<Tree>{
    int x, y, age;
    Tree(int x, int y,int age){
        this.x = x;
        this.y = y;
        this.age =age;
    }

    @Override
    public String toString() {
        return "Tree{" +
                "x=" + x +
                ", y=" + y +
                ", age=" + age +
                '}';
    }

    @Override
    public int compareTo(Tree o) {
        return this.age-o.age;
    }
}
public class Main {
    static int N;
    static int M;
    static int K;
    static int[][] sugar;
    static int[][] addSugarAmount;
    static int[] dx ={-1,-1,0,1,1,1,0,-1};
    static int[] dy ={0,1,1,1,0,-1,-1,-1};
    static ArrayList<Tree> trees;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        sugar = new int[N][N];
        addSugarAmount = new int[N][N];

        for(int r=0; r<N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c=0; c<N; c++){
                sugar[r][c] =5;
                addSugarAmount[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        trees = new ArrayList<>();
        for(int m=0; m<M; m++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            int age = Integer.parseInt(st.nextToken());
            trees.add(new Tree(x,y,age));
        }

        int result = getNumberOfLiveTrees(K);
        bw.write(String.valueOf(result));
        bw.flush();
    }

    static int getNumberOfLiveTrees(int K){
        for(int year =1; year<=K; year++){
            //봄 : 어린나무 먼저 양분을 먹는다
            Collections.sort(trees);

            ArrayList<Tree> deadTrees = new ArrayList<>();
            ArrayList<Tree> liveTrees = new ArrayList<>();

            for(int index =0; index<trees.size();index++){
                Tree currentTree = trees.get(index);
                int x = currentTree.x;
                int y = currentTree.y;
                int age = currentTree.age;

                if(age<=sugar[x][y]){
                    //양분을 먹을 수 있다
                    sugar[x][y] -= age;
                    age +=1;
                    liveTrees.add(new Tree(x,y,age));
                }
                else{
                    //양분을 먹을 수 없다
                    //deadTrees.add(trees.remove(index));
                    deadTrees.add(new Tree(x,y,age));
                }
            }


            //여름
            if(deadTrees.size()>0){
                for(Tree deadTree : deadTrees){
                    int x = deadTree.x;
                    int y = deadTree.y;
                    int age = deadTree.age;

                    sugar[x][y] += (age/2);
                }
            }



            //가을 나무 번식
            int size = liveTrees.size();
            for(int index =0; index<size; index++){
                Tree spreadTree = liveTrees.get(index);
                if(spreadTree.age%5==0){
                   for(int d=0; d<8;d++){
                       int nx = spreadTree.x +dx[d];
                       int ny = spreadTree.y +dy[d];

                       if(nx>=0 && ny>=0 && nx<N && ny<N){
                           liveTrees.add(new Tree(nx,ny,1));
                       }
                   }
                }
            }

            //겨울 - 양분 충전
            for(int r=0;r<N;r++){
                for(int c=0; c<N; c++){
                    sugar[r][c] +=addSugarAmount[r][c];
                }
            }
            trees = liveTrees;
        }

        return trees.size();
    }
    static void printMap(int[][] map){
        for(int r=0; r<map.length; r++){
            for(int c=0; c<map[r].length; c++){
                System.out.print(map[r][c]+ " ");
            }
            System.out.println();
        }
    }
}