백준/16235/Java - 나무 재테크

문제

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

16235번: 나무 재테크

---

 나무들을 어떤 형태로 저장할 것인가를 결정하는 것이 가장 중요한 문제인 듯 하다.

 문제에서 N * N 크기의 땅이 주어지기 때문에 [N][N] 크기의 이차원 배열을 떠올릴 수 있다. 하지만 땅 1칸에 나무가 하나만 있는 것이 아니므로 이차원 배열 위에 나무를 표시하기는 적절치 않다.

 떠올릴 수 있는 것은 LinkedList나 queue 등의 자료구조이다. 나무는 x, y 좌표와 나이라는 속성을 갖기 때문에 이에 맞게 클래스를 선언하고 나무 클래스를 저장할 수 있는 자료구조를 활용하면 된다.

 가장 중요한 조건은 나무는 어린 나무부터 양분을 섭취한다는 조건이다. 즉 '순서' 내지는 '정렬'에 유의해야 한다는 뜻이자 나무는 나이를 기준으로 오름차순 정렬이 되어야 한다는 뜻이다. 나이가 어린 나무부터 탐색해야 어린 나무 먼저 양분을 섭취할 수 있다. 또한 새로 나무를 심을 때, 새로 심는 나무는 무조건 가장 어린 나무이므로 자료 구조의 맨 앞에 추가해준다면 오름차순 순서가 흐트러질 일이 없다.

 정렬을 위해서, 나무 클래스는 Comparable 인터페이스를 implements 하였다(compareTo 메서드 오버라이딩).

class Tree implements Comparable<Tree>{
	int x, y, age;
	public Tree(int x, int y, int age){
		this.x = x;
		this.y = y;
		this.age = age;
	}
	
	@Override
	public int compareTo(Tree t) {
		if(this.age > t.age) return 1;
		else if(this.age < t.age) return -1;
		else return 0;
	}
}

 이렇게 정리가 끝난 뒤에는 문제에서 시키는 대로 구현하면 간단하게 끝날 것이라고 생각하고 봄, 여름, 가을, 겨울을 나누어 메서드를 구현을 했다. 그런데..

public static void spring() {
		for(int i=0; i<trees.size(); i++) {
			Tree cur = trees.get(i);
			int x = cur.x;
			int y = cur.y;
			int age = cur.age;

			//양분이 나이보다 작으면 그 나무는 죽는다...
			if(Map[x][y] < age) {
				deads.add(new Tree(x, y, age));
				trees.remove(i);
			}
			else {
				trees.set(i, new Tree(x, y, age + 1));
				Map[x][y] -= age;
			}
		}
	}

살아있는 나무들의 LinkedList인 trees와 죽은 나무들의 LinkedList인 deads 두 가지를 활용했다.

그러나 위 코드에는 두 가지 문제가 있다. 

1. trees.size()까지 trees를 돌면서 탐색을 하면서 trees.remove로 trees.size를 계속 바꾸고 있기 때문에 전체 trees를 온전히 탐색할 수 없다. 임시 배열에 나무들을 저장했다가 다시 옮기면서 발생하는 시간소요를 걱정하느라 기초적인 실수를 했다.

2. (어차피 1번의 문제 때문에 정답이 틀려 시간초과가 발생하지도 못하겠지만) LinkedList의 get 메서드는 시간복잡도가 O(N). LinkedList는 자료 검색시 처음부터 N번째 까지 탐색하므로 느리다는 문제가 있다.

 

 위의 실수를 수정하여 전체 trees를 온전히 탐색하기 위해 나이가 어린 순서대로 하나씩 빼서 탐색하도록 PriorityQueue를 활용하여 문제를 풀었다. 우선순위 큐는 큐이기 때문에 FIFO 구조를 갖되, 우선순위가 앞서는 객체가 있다면 해당 객체를 더 우선시 하는 자료구조이다. 따라서 우선순위 큐에 담긴 나무 객체들은 항상 나이를 기준으로 정렬된다.

 

PriorityQueue를 활용한 풀이는 메모리 301444 kb 시간 1332 ms 라는 결과가 나왔다.

 

 그러나 시간을 조금 더 단축시킬 방법이 없는지 궁금했다. PriorityQueue는 항상 나이순으로 정렬이 보장되어있다는 장점이 있지만, 반대로 데이터를 추가 할 때마다 정렬을 할테니 시간이 오래걸릴 것이라고 생각했다. 또한 죽은 나무들을 분리해내기 위해 큐에서 객체들을 꺼내 다시 임시 배열에 담고, 다시 큐에 담을 필요가 있을지 생각해보았다.

 

 결국 처음 풀이를 시도했던 것 처럼, LinkedList를 활용하되, 처음 풀이와 같은 문제가 발생하지 않도록 iterator를 활용하여 반복문을 구성하고 죽은 나무들은 나무 객체에 boolean 속성을 주어 구분하였다. 나이순 정렬의 문제는 새 나무를 추가할 때 리스트의 맨 앞에 추가한다면  나무들을 나이 순으로 정렬하는 것은 최초 1회만 시행하면 신경 쓸 필요 없는 것이었다.

 

LinkedList를 활용한 두번째 풀이는 메모리 297748 kb 시간 824 ms 라는 결과가 나왔다. 

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	/*
	PriorityQueue를 활용한 풀이 - 정답.
  메모리 301444 kb 시간	1332 ms
	*/
	static int N, M, K;
	static int[][] A; //추가할 양분 배열 
	static int[][] Map;//땅 
	static Queue<Tree> trees;
	static LinkedList<Tree> deads;
	/*
	(r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1)
	 */
	static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, 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];
		Map = new int[N][N];
		//나무들은 나이 기준 오름차순 정렬되어야 하기 때문에 우선순위 큐를 활용. 
		trees = new PriorityQueue<>();
		//죽은 나무들은 순서가 상관없음. 
		deads = new LinkedList<>();
		
		//A배열 초기화. 땅에는 양분이 5씩 있다. 
		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());
				Map[i][j] = 5;
			}
		}
		//나무 정보 
		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());
			
			Tree tree = new Tree(x, y, age);
			trees.add(tree);
		}
		
		for(int i=0; i<K; i++) {
			spring();
			summer();
			autumn();
			winter();
		}
		sb.append(trees.size());
		System.out.println(sb);
	}
	
	public static void spring() {
		LinkedList<Tree> temp = new LinkedList<>();
		
		while(!trees.isEmpty()) {
			Tree tree =  trees.poll();
			if(Map[tree.x][tree.y] < tree.age) deads.add(tree);
			else {
				temp.add(new Tree(tree.x, tree.y, tree.age+1));
				Map[tree.x][tree.y] -= tree.age;
			}
		}
		trees.addAll(temp);
	}
	
	public static void summer() {
		while(!deads.isEmpty()) {
			Tree dead = deads.poll();
			Map[dead.x][dead.y] += dead.age / 2;
		}
	}
	
	public static void autumn() {
		LinkedList<Tree> temp = new LinkedList<>();
		
		while(!trees.isEmpty()) {
			Tree tree = trees.poll();
			if(tree.age % 5 == 0) {
				for(int j=0; j<8; j++) {
					int x = tree.x + dx[j];
					int y = tree.y + dy[j];
					if(x >= 0 && y >= 0 && x < N && y < N) temp.add(0, new Tree(x, y, 1));
				}
			}
			temp.add(tree);
		}
		trees.addAll(temp);
	}
	public static void winter() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				Map[i][j] += A[i][j]; 
			}
		}
	}
		
}

class Tree implements Comparable<Tree>{
	int x, y, age;
	
	public Tree(int x, int y, int age){
		this.x = x;
		this.y = y;
		this.age = age;
	}
	
	@Override
	public int compareTo(Tree t) {
		if(this.age > t.age) return 1;
		else if(this.age < t.age) return -1;
		else return 0;
	}
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	/*
	LinkedList를 활용한 풀이 - 정답
  메모리 297748 kb	824 ms
	*/
	static int N, M, K;
	static int[][] A; //추가할 양분 배열 
	static int[][] Map;//땅 
	static LinkedList<Tree> trees;
	static LinkedList<Tree> deads;
	/*
	(r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1)
	 */
	static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, 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];
		Map = new int[N][N];
		//나무들은 나이 기준 오름차순 정렬되어야 하기 때문에 뒤에서 정렬해줌. 
		trees = new LinkedList<>();
		//죽은 나무들은 순서가 상관없음. 
		deads = new LinkedList<>();
		
		//A배열 초기화. 땅에는 양분이 5씩 있다. 
		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());
				Map[i][j] = 5;
			}
		}
		//나무 정보 
		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());
			
			Tree tree = new Tree(x, y, age);
			trees.add(tree);
		}
		//나이 기준 오름차순으로 정렬. 초기에 한번만 해주면 된다.
		Collections.sort(trees);
		
		for(int i=0; i<K; i++) {
			spring();
			summer();
			autumn();
			winter();
		}
		sb.append(trees.size());
		System.out.println(sb);
	}
	
	public static void spring() {
		for(Tree tree : trees) {
			if(Map[tree.x][tree.y] < tree.age) tree.dead = true;
			else {
				Map[tree.x][tree.y] -= tree.age;
				tree.age++;
			}
		}
	}
	
	public static void summer() {
		Iterator<Tree> iter = trees.iterator();
		while(iter.hasNext()) {
			Tree tree = iter.next();
			if(tree.dead) {
				Map[tree.x][tree.y] += tree.age / 2;
				iter.remove();
			}
		}
	}
	
	public static void autumn() {
		LinkedList<Tree> news = new LinkedList<>();
		
		Iterator<Tree> iter = trees.iterator();
		while(iter.hasNext()) {
			Tree tree =  iter.next();
			if(tree.age % 5 == 0) {
				for(int j=0; j<8; j++) {
					int x = tree.x + dx[j];
					int y = tree.y + dy[j];
					if(x >= 0 && y >= 0 && x < N && y < N) news.add(0, new Tree(x, y, 1));
				}
			}
		}
		trees.addAll(0, news);
	}
	public static void winter() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				Map[i][j] += A[i][j]; 
			}
		}
	}
		
}

class Tree implements Comparable<Tree>{
	int x, y, age;
	boolean dead = false;
	public Tree(int x, int y, int age){
		this.x = x;
		this.y = y;
		this.age = age;
	}
	
	@Override
	public int compareTo(Tree t) {
		if(this.age > t.age) return 1;
		else if(this.age < t.age) return -1;
		else return 0;
	}
}