백준 16235번 <나무 재테크>

최악의 시뮬레이션.... 시간 초과가 무엇인지를 제대로 보여주는 시뮬레이션이었다...

이문제를 풀면서 느낀 건 시간!! 시간!! 시간이다..

이 문제의 핵심은 시뮬레이션대로 어떻게 시간을 줄여줄 건인가 였다.

문제 풀이

1. 모든 나무들을 live라는 queue에 넣어주고 나이가 작은 순으로 collections.sort 해준다.
2. 4 계절대로 흐름을 구성한다.
3. 봄 --> live큐에서 꺼내서 양분을 먹을 수 있으면 나이를 먹고 live에 다시 넣어주고 안되면 die queue에 넣어준다.
4. 여름 --> die 큐에서 꺼내서 양분으로 준다.
5. 가을(가장 까다로움) -->
   1. 작은 순으로 다시 live에 넣어줘야 하기 때문에 p라는 큐를 만든다.
   2. *live에서 꺼낸 큐를 p에 넣고 5로 나눠진다면 8방향 중 가능한 곳의 좌표와 함께 live에 넣어준다. (그 이유는 어차피 작은 순서기 때문에 새로 생긴 게 더 작기 때문에) *
   3. ** p의 큐의 값들을 live로 옮긴다.**
6. 겨울 --> 양분을 다시 채워준다.

나무 좌표와 나이를 추가하기 위한 클래스를 만든다.

봄--> 나이 작은 순으로 정렬되어 있기 때문에 꺼내서 확인 후 양분 섭취 가능하면 1 더 해서 다시 넣어주고 안되면 die큐에

여름-->간단하다.

겨울--> 양분 보충

전체 코드

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static class skan1 implements Comparable<skan1> {
		int x;
		int y;
		int year;

		public skan1(int x, int y, int year) {
			this.x = x;
			this.y = y;
			this.year = year;
		}
		@Override
		public int compareTo(skan1 o) {
			// TODO Auto-generated method stub
			if (this.year > o.year)
				return 1;
			else if(this.year == o.year)
				return 0;
			return -1;
		}
	}

	static Queue<skan1> live = new LinkedList<skan1>();
	static Queue<skan1> die = new LinkedList<skan1>();
	static int plus[][], map[][],div[][]= {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
	static int N, M, K;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		K = kb.nextInt();
		map = new int[N][N];
		plus = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = 5;
				plus[i][j] = kb.nextInt();
			}
		}
		for (int i = 0; i < M; i++) {
			live.add(new skan1(kb.nextInt()-1, kb.nextInt()-1, kb.nextInt()));
		}
		Collections.sort((List<skan1>) live);

		start();
		System.out.println(live.size());
	}

	public static void start() {
		int n = 0;
		while (n < K) {
			int i = 0;
			int si=live.size();
			while (i <si) {
				skan1 ki=live.remove();
				if (map[ki.x][ki.y] >= ki.year) {
					map[ki.x][ki.y] -= ki.year;
					ki.year++;
					live.add(ki);
				} else {
					die.add(ki);
				}
				i++;
			} // 봄
			while (!die.isEmpty()) {
				skan1 ki=die.remove();
				map[ki.x][ki.y] += ki.year/2;
			} // 여름
			i = 0;
			si=live.size();
			Queue<skan1> p = new LinkedList<skan1>();
			while (i<si) {
				skan1 ki=live.remove();
				if (ki.year % 5 == 0) {
					for (int h = 0; h < 8; h++) {
						int x1=ki.x;
						int y1=ki.y;
						x1+=div[h][0];
						y1+=div[h][1];
						if(x1>=0&&x1<N&&y1>=0&&y1<N) {
							live.add(new skan1 (x1,y1,1));
						}
					}
				}
				p.add(ki);
				i++;
			}
			while(!p.isEmpty()) {
				live.add(p.remove());
			}
			//가을
			for(int j=0;j<N;j++) {
				for(int k=0;k<N;k++) {
					map[j][k]+=plus[j][k];
				}
			}//겨울
			n++;
		}
	}

}