구현

백준 16235번 구현 문제를 Java로 풀어보았다.
어떤 자료구조를 이용해서 나무들을 표현할지 고민하게 된 문제였다.

한 칸에 여러 나무가 있다면?

처음에는 LinkedList[][] 로 선언해서 나무 정보들을 각 위치에 추가해나갈까 고민했는데 그러면 나무가 심기지 않은 위치들에 대한 잉여 자원이 너무 많아지겠다는 생각에 다른 방법을 고민했다.

결국 한 칸에 여러 나무를 심을 때 고려해야 할 것은 하나다.
여러 나무 중에 어린 놈을 먼저 먹여야 한다는 것.

그렇다면 먹이를 줄 때 어린 놈들이 젤 앞에 있으면 된다. 따라서 나무들을 줄 세우되 새롭게 태어난 놈들을 앞에다 두면 되기 때문에 새롭게 태어난 어린 놈들을 늙은 놈들 앞에다가 통째로 갖다 세워두면 된다.

이는 가을에 발생하는 일인데 다른 것보다 이 부분만 먼저 코드를 확인해보자.

/** Autumn */
            int[][] move = { {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1} };
            LinkedList<Tree> new_born = new LinkedList<>();
            for(Tree t: trees){
                int r = t.row; int c = t.col; int age = t.age;

                if(age%5 == 0){
                    for (int i = 0; i < 8; i++) {
                        int n_row = r + move[i][0];
                        int n_col = c + move[i][1];
                        if(n_row<1 || n_row>n || n_col<1 || n_col>n)    continue;
                        new_born.add(new Tree(n_row, n_col, 1));
                    }
                }
            }
            trees.addAll(0, new_born); // 어린이들을 앞에다 갖다붙여

다른 계절의 로직은 간단하다. 그냥 문제 조건대로만 작성하면 되고 내가 고민했던 유일한 부분은 가을이었다.

Iterator 사용

그동안은 Iterator를 딱히 사용하지 않아도 다 풀리는 문제들만 풀어왔는데 이번 문제를 통해 Iterator를 사용해봤다.

hasNext(), next(), remove() 이 세 개만 사용하는데 삽입 및 변경을 하지 않을 경우, 즉 이 문제의 봄의 작업을 처리해줄 때가 딱 적절한 경우다.

왔다갔다 할 필요없이 앞에서부터 쭉 뒤로 가며 제거만이 발생 가능한 유일한 작업일 경우에 사용할 수 있으며 어떤 종류의 Collection이든 사용 가능하다는 표준이 되는 도구다.

/** Spring */
            Iterator<Tree> it = trees.iterator();
            while(it.hasNext()){
                Tree cur_tree = it.next();
                int r = cur_tree.row;   int c = cur_tree.col;   int age = cur_tree.age;
                if(nutrition[r][c]-age<0){ // 먹이가 부족해요
                    dead_trees.add(cur_tree); // 그럼 죽어야지
                    it.remove();
                }
                else{ // 먹이 충분하면
                    nutrition[r][c] -= age;
                    cur_tree.age += 1; // 한 살 더 머겅
                }
            }

먼저 LinkedList를 이용했다가 ArrayList를 사용해도 똑같으려나 싶어서 바꿔 제출해보았더니 시간초과가 났다. 아마 앞에서부터 순서대로만 탐색하면 되는 문제기 때문에 LinkedList와 달리 어느 위치든 갈 수 있는 ArrayList를 쓰면 시간이 더 걸려서 그런 것 같다.

아래는 내가 제출한 코드다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.Iterator;

public class boj16235 {
    static int n,m,k;
    static int[][] feed, nutrition;
    static LinkedList<Tree> trees = new LinkedList<>();
    static Queue<Tree> dead_trees = new LinkedList<>();

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        n = Integer.parseInt(stk.nextToken()); m = Integer.parseInt(stk.nextToken()); k = Integer.parseInt(stk.nextToken());
        feed = new int[n+1][n+1]; nutrition = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            stk = new StringTokenizer(bfr.readLine());
            for(int j=1; j<=n; j++){
                feed[i][j] = Integer.parseInt(stk.nextToken());
                nutrition[i][j] = 5;
            }
        }

        for(int i=0; i<m; i++){
            stk = new StringTokenizer(bfr.readLine());
            int r = Integer.parseInt(stk.nextToken());  int c = Integer.parseInt(stk.nextToken());  int age = Integer.parseInt(stk.nextToken());
            trees.add(new Tree(r,c,age));
        }

        afterKYears();
        bfw.write(String.valueOf(trees.size()));
        bfw.close();
    }

    static void afterKYears(){
        int year = 0;
        while(true){
            if(year==k) return;

            /** Spring */
            Iterator<Tree> it = trees.iterator();
            while(it.hasNext()){
                Tree cur_tree = it.next();
                int r = cur_tree.row;   int c = cur_tree.col;   int age = cur_tree.age;
                if(nutrition[r][c]-age<0){ // 먹이가 부족해요
                    dead_trees.add(cur_tree); // 그럼 죽어야지
                    it.remove();
                }
                else{ // 먹이 충분하면
                    nutrition[r][c] -= age;
                    cur_tree.age += 1; // 한 살 더 머겅
                }
            }

            /** Summer */
            while(!dead_trees.isEmpty()){
                Tree dead = dead_trees.poll();
                nutrition[dead.row][dead.col] += dead.age/2;
            }

            /** Autumn */
            int[][] move = { {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1} };
            LinkedList<Tree> new_born = new LinkedList<>();
            for(Tree t: trees){
                int r = t.row; int c = t.col; int age = t.age;

                if(age%5 == 0){
                    for (int i = 0; i < 8; i++) {
                        int n_row = r + move[i][0];
                        int n_col = c + move[i][1];
                        if(n_row<1 || n_row>n || n_col<1 || n_col>n)    continue;
                        new_born.add(new Tree(n_row, n_col, 1));
                    }
                }
            }
            trees.addAll(0, new_born);

            /** Winter */
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++)
                    nutrition[i][j] += feed[i][j];
            }

            year++;
        }
    }

    static class Tree {
        int row; int col; int age;

        Tree(int r, int c, int age){
            this.row = r;
            this.col = c;
            this.age = age;
        }
    }
}

오늘 배운 것

1. Iterator는 Collection의 표준이다.
2. 앞에서부터 쭉 순서대로 순회할 때는 LinkedList를 쓰자.