[백준] G4 16235 나무 재테크 (java)

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

16235번: 나무 재테크

 

풀이

 

1) 준비물을 준비한다.

• 나무의 상태를 저장할 클래스 Tree, <- Comparable 인터페이스를 통해 나이의 오름차순으로 적용해야 한다.
• 나무들을 담을 List<Tree> list
• 새로 생성되는 나무를 저장할 List<Tree> temp
• 현재 양분의 양을 나타내는 map[][]
• 죽은 나무의 양분을 저장하는 dead[][]

2) K 가 0이 될때 까지 봄, 여름, 가을, 겨울의 상황을 적용한다. 봄과 가을을 묶고 여름과 겨울을 묶어서 풀면 편해진다.

2-0) list에서 하나씩 뽑는다. list.get(i) 로 탐색하는 순간 시간초과다. LinkedList의 get()은 O(N) 이기 때문이다. 따라서 Collection에 저장된 요소를 읽을 수 있는 Iterator 를 이용해야 한다. 하지만 삽입 연산에서 LinkedList는 O(1) 이므로 LinkedList를 사용해야한다. (참고로, ArrayList의 get()은 O(1), 삽입은 O(N) 이다.)

2-1) 봄과 가을 : list를 갱신한다.

2-2) 여름과 겨울 : map을 갱신한다.

3) list의 크기를 출력한다.

 

주의사항

 

1) 어지간한 풀이는 시간초과가 난다.

2) 다른 풀이를 보면 deque를 이용했는데 list로도 가능하다. 단, 반드시 LinkedList 여야만 한다. (ArrayList ㄴㄴ)

 

package com.baekJoon;

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

public class BJ_G4_16235_나무재테크 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M,K,map[][], add[][], dead[][]; // map 은 양분이다.
	static List<Tree> list = new LinkedList<>();
	static List<Tree> temp = new LinkedList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		K = Integer.parseInt(tokens.nextToken());
		map = new int[N][N];
		add = new int[N][N];
		dead = new int[N][N];
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				map[r][c] = 5; //가장 처음에 양분은 모든 칸에 5만큼 들어있다.
			}	
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<N; c++) {
				add[r][c] = Integer.parseInt(tokens.nextToken());
			}	
		}
		for(int m=0; m<M; m++) {
			tokens = new StringTokenizer(input.readLine());
			int r = Integer.parseInt(tokens.nextToken())-1;
			int c = Integer.parseInt(tokens.nextToken())-1;
			int age = Integer.parseInt(tokens.nextToken());
			list.add(new Tree(r, c, age));
		} // 입력 끝
		Collections.sort(list); // 어린 나무순으로 정렬
		
		while(K-- > 0) {
			springAndfall();
			summerAndwinter();
			if(list.size() == 0) break;
		}
		System.out.println(list.size());
	}
	private static void springAndfall() {
		Tree tree;
		for(Iterator<Tree> iter = list.iterator(); iter.hasNext();) {
			tree = iter.next();
			int r = tree.r;
			int c = tree.c;
			int age = tree.age;
			
			if(map[r][c] < age) { // 자기 나이보다 양분이 적을 경우
				dead[r][c] += age/2; // 쥬금 + 더해질 양분 기억
				iter.remove(); // 해당 list의 데이터도 삭제된다.
			}else { // 안 죽을 경우 양분이 빨리고 나이가 증가한다.
				map[r][c] -= age;
				tree.age++;
				if(tree.age%5 == 0) {
					for(int d=0; d<8; d++) {
						int nr = r + dr[d];
						int nc = c + dc[d];
						if(isIn(nr, nc)) {
							temp.add(0, new Tree(nr, nc, 1));
						}
					}
				}
			}
			
		}
		list.addAll(0, temp);
		temp.clear();
	}
	private static void summerAndwinter() {
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				map[r][c] += dead[r][c];
				map[r][c] += add[r][c];
				dead[r][c] = 0;
			}	
		}
	}
	static int dr[] = {-1,-1,-1,0,0,1,1,1};
	static int dc[] = {-1,0,1,-1,1,-1,0,1};
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<N && c<N);
	}
	static class Tree implements Comparable<Tree>{
		int r;
		int c;
		int age;

		public Tree(int r, int c, int age) {
			super();
			this.r = r;
			this.c = c;
			this.age = age;
		}

		@Override
		public String toString() {
			return "Tree [r=" + r + ", c=" + c + ", age=" + age + "]";
		}

		@Override
		public int compareTo(Tree o) {
			return Integer.compare(this.age, o.age);
		}
	}
	static String src =
			"5 2 6\r\n"
			+ "2 3 2 3 2\r\n"
			+ "2 3 2 3 2\r\n"
			+ "2 3 2 3 2\r\n"
			+ "2 3 2 3 2\r\n"
			+ "2 3 2 3 2\r\n"
			+ "2 1 3\r\n"
			+ "3 2 3";
}

 

후기

 

 시간초과로 매우 고생한 문제이다. 이 문제를 품으로써

1. list.get() 보다 효율적인 방법 -> Iterator의 활용 법을 알 수 있었다.
   • for(Iterator<Tree> iter = list.iterator(); iter.hasNext();) { } 
2. LinkedList와 ArrayList의 차이를 제대로 짚고 넘어갈 수 있었다.
   • LinkedList : 탐색할 때 O(N), 삽입할 때 O(1)
   • ArrayList : 탐색할 때 O(1), 삽입할 때 O(N)

정말 의미 있는 문제였다.