[삼성SW테스트] 백준 16235 나무재태크(시뮬레이션)

 

 

백준 시뮬레이션 문제

#16235- 나무재태크

 

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

 

사용한 개념

 

시뮬레이션 문제입니다. 문제에서 주어진 조건에 따라 각 단계별 로직을 짜고 전체 프로세스를 만드는 문제입니다. 별다른 개념은 필요하지 않습니다. if문과 for문 등등의 조건/반복문을 이용해서 자기 스타일대로 짜면 되는것이죠..

이 문제에서 힘들었던 점은 시간초과를 어떻게 방지하냐 입니다.. 제가 삽질하면서 느꼈던 내용은 아래와 같습니다.

 

1. ArrayList보단 LinkedList가 성능이 더 좋다.

2. LinkedList를 자주 add하고 poll하는것은 많은 스택오버플로우를 낼 수 있다. 따라서 get으로 접근하거나 iterator를 적절히 사용하는 것이 성능에 좋다.

3. 센스있게 답이 구해졌다 싶으면 바로 프로세스를 종료할 수 있는 로직을 짜야한다.

 

아래는 전체 소스입니다.

 

package RESAMSUNG;

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

public class BackJoon_16235 {

	static int[][] map;
	static int[][] nutrient;
	static int N,M,K =0;
	static int[] dX = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int[] dY = {-1, 0, 1, -1, 1, -1, 0, 1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//N:크기,M:나무수,K:시간
		String str = br.readLine();
		String[] strArr = str.split(" ");
		 N = Integer.parseInt(strArr[0]);
		 M = Integer.parseInt(strArr[1]);
		 K = Integer.parseInt(strArr[2]);
		
		map = new int[N][N];
		nutrient = new int[N][N];
		for(int i=0; i<N; i++){
			String str1 = br.readLine();
			String[] strArr1 = str1.split(" ");
			for(int j=0; j<N; j++){
				nutrient[i][j] = Integer.parseInt(strArr1[j]);
				map[i][j] = 5; //최초 기초 양분 5 초기화
			}
		}
		
		LinkedList<Tree> treeList = new LinkedList<>();
		for(int i=0; i<M; i++){
			String str1 = br.readLine();
			String[] strArr1 = str1.split(" ");
			int x = Integer.parseInt(strArr1[0]);
			int y = Integer.parseInt(strArr1[1]);
			int age = Integer.parseInt(strArr1[2]);
			treeList.add(new Tree(x-1, y-1, age, 1));

		}
		
		for(int k=0; k<K; k++){
			//봄
			//나무는 자신의 나이만큼 양분을 흡수, 나이+1 (어린나무 순)
			//만약 양분을 못먹으면 즉사
			LinkedList<Tree> newTreeList = new LinkedList<>();
			for(Tree t : treeList){
				if(map[t.x][t.y] >= t.age){
					map[t.x][t.y] -= t.age;
					t.age++;
				}else{
					t.life = 0;
				}
			}
			
			//여름
			//죽는나무/2 만큼의 양분이 해당 칸에 쌓임
			for(Iterator<Tree> itt = treeList.iterator(); itt.hasNext();){
				Tree t= itt.next();
				if(t.life == 0){
					map[t.x][t.y] += t.age / 2;
					itt.remove();;
				}
			}
			
			//가을
			//나무나이가 5인경우 8개영역에 나이1인 나무를 뿌림
			for(Tree t : treeList){
				if(t.age % 5 == 0)
				for(int j=0; j<8; j++){
					int nX = t.x + dX[j];
					int nY = t.y + dY[j];
					if(-1<nX && nX<N && -1<nY && nY<N){
						newTreeList.add(new Tree(nX, nY, 1, 1));
					}
				}
			}
			treeList.addAll(0, newTreeList);

			if(k==K-1) {
				System.out.println(treeList.size());
				return;
			}
			//겨울
			//S2D2 기계가 사용자 지정한 양분을 보충
			for(int i=0; i<N; i++){
				for(int j=0; j<N; j++){
					map[i][j] += nutrient[i][j];
				}
			}
		
		}

	}
	
	static class Tree{
		int x;
		int y;
		int age;
		int life;
		public Tree(int x, int y, int age, int life) {
			super();
			this.x = x;
			this.y = y;
			this.age = age;
			this.life = life;
		}
		
	}

}