[백준 16235] 나무 재테크

문제 링크: https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

---

풀이

문제 내용과 구현 자체는 그리 어렵지 않지만, 시간 제한이 빡빡한 문제였다. 그래서 어떤 자료구조를 선택할지 많이 고민했다. 

문제에서 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 고 했으므로, 나이가 어린 나무부터 순회해야 한다. 하지만 매년 나무를 나이 순으로 정렬하면 시간 초과가 날 것 같았기 때문에, 최초 1번만 정렬한 뒤에 시뮬레이션을 진행할 수 있는 방법을 찾아야 했다.

결론부터 말하자면 Deque을 사용했다. 별도의 정렬 없이 시뮬레이션을 진행하려면, head와 tail 양 끝에서 원소를 넣고 빼야 했기 때문이다. 덱의 head에서 tail로 갈수록 나무의 나이가 많아진다고 가정해보자.

• head에서 나무를 꺼내 양분을 먹이고 나이를 증가시킨 뒤, tail에 넣어주면 나이 순 정렬을 유지할 수 있다.
• 나이가 1인 나무가 추가되는 경우에도, head에 원소를 넣어주면 나이 순 정렬을 유지할 수 있다. 

(0) 트리 클래스

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

	@Override
	public int compareTo(Tree o) {
		return this.age - o.age;
	}
}

문제에 나이가 적은 나무부터 입력으로 주어진다는 조건이 없어서, 최초 1번은 정렬이 필요하다. 때문에 Comparable 인터페이스를 상속받아 compareTo() 함수를 구현해주었다.

(1) 봄

• 덱의 머리에서 나무를 하나 꺼낸다.
  • 땅에 양분이 부족하다면 deadTree에 나무를 추가한다.
  • 양분이 충분하다면, 땅의 양분을 감소시키고 나무의 나이를 증가시킨 후, 덱의 꼬리에 나무를 넣어준다.

public static List<Tree> spring() {
    List<Tree> deadTree = new ArrayList<>();

    int size = trees.size();
    for (int i=0; i<size; i++) {
        Tree tree = trees.poll();
        if(tree.age > nutrient[tree.x][tree.y]) {
            deadTree.add(tree);
            continue;
        }
        nutrient[tree.x][tree.y] -= tree.age;
        tree.age++;
        trees.add(tree);
    }

    return deadTree;
}

(2) 여름

• 봄에 죽은 나무들을 양분으로 변화시킨다.

public static void summer(List<Tree> deadTree) {
    for (Tree tree : deadTree) {
        nutrient[tree.x][tree.y] += (tree.age/2);
    }
}

(3) 가을

• 덱에 담긴 나무를 순회한다.
• 나무의 나이가 5의 배수라면, 해당 나무를 copiedTree에 넣어준다.
• copiedTree의 나무들을 덱의 머리에 넣어준다.

public static void fall() {
    List<Tree> copiedTree = new ArrayList<>();
    for (Tree tree : trees) {
        if(tree.age%5 == 0) {
            copiedTree.add(tree);
        }
    }

    for (Tree tree : copiedTree) {
        for (int i=0; i<8; i++) {
            int nx = tree.x+dx[i];
            int ny = tree.y+dy[i];
            if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
            trees.addFirst(new Tree(nx, ny, 1));
        }
    }
}

(4) 겨울

• 땅에 양분을 추가한다.

public static void winter() {
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            nutrient[i][j] += A[i][j];
        }
    }
}

---

전체 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.StringTokenizer;

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

	@Override
	public int compareTo(Tree o) {
		return this.age - o.age;
	}
}

public class Main {
	static int N, M, K;
	static int[] dx = {-1,-1,-1,0,0,1,1,1}, dy = {-1,0,1,-1,1,-1,0,1};
	static int[][] A, nutrient;
	static Deque<Tree> trees = new ArrayDeque<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		A = new int[N][N];
		nutrient = new int[N][N];
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=0; j<N; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int i=0; i<N; i++) {
			Arrays.fill(nutrient[i], 5);
		}
		
		List<Tree> treeList = new ArrayList<>();
		for (int i=0; i<M; i++) {
			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());
			treeList.add(new Tree(x, y, age));
		}
		
		Collections.sort(treeList); // 나이 순 정렬
		for (Tree tree : treeList) {
			trees.add(tree);
		}
		
		while(K>0) {
			List<Tree> deadTree = spring();
			summer(deadTree);
			fall();
			winter();
			K--;
		}
		
		System.out.println(trees.size());
		
	}
	
	public static List<Tree> spring() {
		List<Tree> deadTree = new ArrayList<>();
		
		int size = trees.size();
		for (int i=0; i<size; i++) {
			Tree tree = trees.poll();
			if(tree.age > nutrient[tree.x][tree.y]) {
				deadTree.add(tree);
				continue;
			}
			nutrient[tree.x][tree.y] -= tree.age;
			tree.age++;
			trees.add(tree);
		}
		
		return deadTree;
	}
	
	public static void summer(List<Tree> deadTree) {
		for (Tree tree : deadTree) {
			nutrient[tree.x][tree.y] += (tree.age/2);
		}
	}
	
	public static void fall() {
		List<Tree> copiedTree = new ArrayList<>();
		for (Tree tree : trees) {
			if(tree.age%5 == 0) {
				copiedTree.add(tree);
			}
		}
		
		for (Tree tree : copiedTree) {
			for (int i=0; i<8; i++) {
				int nx = tree.x+dx[i];
				int ny = tree.y+dy[i];
				if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
				trees.addFirst(new Tree(nx, ny, 1));
			}
		}
	}
	
	public static void winter() {
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				nutrient[i][j] += A[i][j];
			}
		}
	}
}