[백준] 16235 - 나무 재테크 (JAVA)

1. 소요시간 : 1시간 40분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 3
4. 문제 유형 : 구현, 자료 구조, 시뮬레이션
5. 다른 사람의 풀이를 참고 했는가 ? : O
   -> 시간 초과가 나서 그 부분을 해결하기 위해 질문게시판 참고
6. 문제 링크 : https://www.acmicpc.net/problem/16235
7. 푼 날짜 : 2023.05.01

1. 사용한 자료구조 & 알고리즘

큐, 구현, 시뮬레이션

2. 사고과정

spring,summer,autumn, winter 를 각각 처리해 주고
문제에 있는 그대로를 구현하면 되므로 전체적으로는 45분 만에 끝냈다.
하지만 제출을 해도 40% 정도에서 시간 초과가 발생했고
정렬을 하는 부분에서 시간초과가 났을 것으로 예상은 했으나
이를 어떻게 개선해야할지를 떠올리지 못해서 질문게시판을 참고했다.

참고한 내용은 나이가 1인 나무들은 정렬할 필요가 없으므로, 따로 처리해 주는 것이다. 그렇게 하면 정렬의 범위를 크게 줄일 수 있다.

3. 풀이과정

1. 나무들을 정렬한다. (나이순, 나이가 1인것들은 제외)
2. 나이가 1인 나무들이 있다면, 먼저 처리하는데 양분이 1이상이라면 나이가 2가 된다.
3. 나이가 2 이상인 나무들은 양분이 나이 이상이라면 나이를 1증가시키고, 아니라면 죽은 나무에 추가한다.
4. (죽은나무의 나이 / 2) 만큼 양분을 증가시킨다.
5. 나무들을 보고, 나이가 5의 배수라면, 나이가 1인 나무들에 추가시킨다.
6. 해당 좌표에 할당된 값만큼 양분을 증가시킨다.

[1,2,3] - Spring
[4] - Summer
[5] - Autumn
[6] - Winter

4. 소스코드

import java.util.*;
import java.io.*;

public class Main{
	
	static int land[][];
	static int plus[][];
	static LinkedList<Integer[]> tree=new LinkedList<>();
	static LinkedList<Integer[]> deadTree=new LinkedList<>();
	static  Queue <Integer[]> queue=new LinkedList<>();
	static int cnt = 0;
	static int dy[] = {-1,-1,0,1,1,1,0,-1};
	static int dx[] = {0,1,1,1,0,-1,-1,-1};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		int K=Integer.parseInt(st.nextToken());

		land=new int[N+1][N+1];
		plus=new int[N+1][N+1];

		
		for(int i=1;i<land.length;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=1;j<land[0].length;j++) {
				plus[i][j] = Integer.parseInt(st.nextToken());
				land[i][j] = 5;
			}
		}
		
		
		for(int i=0;i<M;i++) {
			st=new StringTokenizer(br.readLine());
			int x=Integer.parseInt(st.nextToken());
			int y=Integer.parseInt(st.nextToken());
			int z=Integer.parseInt(st.nextToken());
			tree.add(new Integer[] {x,y,z});
			
		}
		

		for(int i=0;i<K;i++) {
			
			//나무가 없다면 , 멈춘다
			if(tree.size()==0&&queue.size()==0) break;
			Spring();
			Summer();
			Autumn();
			Winter();
			
		}
		//나무의 개수를 출력
		System.out.println(tree.size()+queue.size());

		
	}
	public static void Spring() {
		//나무들을 정렬한다. 나이 수가 적은 순서대로
		Collections.sort(tree,new Comparator<>() {
			@Override
			public int compare(Integer[] n1,Integer[] n2) {
				if(n1[2]>n2[2])
					return 1;
				else if(n1[2]==n2[2])
					return 0;
				else
					return -1;
			}
		});
		
		//임시저장할 곳
		LinkedList<Integer[]> temp=new LinkedList<>();
		
		//나이가 1인 나무들은 정렬할 필요가 없으니 따로 처리.
		//땅의 양분이 1 이상이면, 나이가 2가 됨
		while(!queue.isEmpty()) {
			Integer poll[]=queue.poll();
			int nowY=poll[0];
			int nowX=poll[1];
			if(land[nowY][nowX]>0) {
				land[nowY][nowX]-=1;
				temp.add(new Integer[] {nowY,nowX,2});
			}
		}
		
		
		while(!tree.isEmpty()) {
			Integer poll[]=tree.pollFirst();
			int nowY=poll[0];
			int nowX=poll[1];
			int age=poll[2];
			
			//양분이 나이 이상이면, 나이 1증가, 양분 감소
			if(land[nowY][nowX]>=age) {
				land[nowY][nowX]-=age;
				temp.add(new Integer[] {nowY,nowX,age+1});
			}
			//아니라면 죽은 나무에 추가
			else {
				deadTree.add(new Integer[] {nowY,nowX,age});
			}
			
		}
		
		//임시저장한 것을 다시나무에 저장
		while(!temp.isEmpty()) {
			tree.add(temp.removeFirst());
		}
		
		
		
		
	}
	
	
	public static void Summer() {
		//죽은 나무의 나이/2 만큼 양분 증가
		while(!deadTree.isEmpty()) {
			Integer temp[]=deadTree.pollFirst();
			int nowY=temp[0];
			int nowX=temp[1];
			int age=temp[2];
			land[nowY][nowX] += (age/2);
		}
		
	}
	
	public static void Autumn() {
		LinkedList<Integer[]> temp=new LinkedList<>();
		
		while(!tree.isEmpty()) {
			Integer poll[]= tree.pollFirst();
			int nowY=poll[0];
			int nowX=poll[1];
			int age = poll[2];
			
			//나이가 5의 배수라면
			if(age%5==0) {
			
				for(int i=0;i<dx.length;i++) {
					int nextY=nowY+dy[i];
					int nextX=nowX+dx[i];
					
					if(nextY<1||nextX<1||nextY>=land.length||nextX>=land[0].length)
						continue;
					
					//나이가 1인 나무에 추가
					queue.add(new Integer[] {nextY,nextX});
					
				}
			}//
			
			temp.add(poll);
			
		}
		
		while(!temp.isEmpty()) {
			tree.add(temp.pollFirst());
		}
		
		
	}
	public static void Winter() {
		//양분 증가
		for(int i=1;i<plus.length;i++) {
			for(int j=1;j<plus[0].length;j++) {
				land[i][j] += plus[i][j];
			}
		}
		
	}


}

5. 결과

계속 시간초과가 나서 질문게시판을 참고했고,
그 결과 1316ms 로 정답을 받았다.

그 후 인터넷의 다른 사람 풀이를 제출했을 때 860ms 가 나왔다.

6. 회고

이 문제들에 대해서 나무들의 값을 정렬하지 않고도 풀 수 있다는 글을 봤는데, 아직까지는 어떻게 그렇게 한 것인지 모르겠다. 그에 대해서 추가로 공부해 볼 예정이다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212