구현
백준 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;
}
}
}
오늘 배운 것
- Iterator는 Collection의 표준이다.
- 앞에서부터 쭉 순서대로 순회할 때는 LinkedList를 쓰자.
