BOJ - 나무 재테크 16235번 (JAVA)

❓ 문제 - 백준 나무재테크 16235번 - JAVA 풀이법

출처 

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

16235번: 나무 재테크

 

 

📝 문제해결법

1. 이 문제는 구현 + 자료구조(queue)로 풀었다.

• 나무들은 Queue에 Tree 객체 형태로 관리한다.
• 1년마다 영양분을 뿌릴 양을 add 2차원 배열에 저장한다.
• map 2차원배열로 땅에 대한 양분정보를 저장한다.
• 봄에 만약 한 1*1 구역에 여러 나무가 심어져있다면 양분을 먼저 먹는 건 나이가 적은 나무라고 했기 때문에 정렬이 필요하다. 하지만 매번 년도마다 정렬하고 관리한다면 시간에서 터진다..
• 따라서 처음 tree 정보를 queue에 넣을 때 나이의 오름차순 순으로 정렬한다. 
• 그 후 1년 과정 안에서 봄, 여름, 가을, 겨울에 맞춰 구현한다.
• 봄에서 만약 큐에서 꺼낸 나무가 해당 지역의 양분보다 나이가 많다면 죽은 나무 dead 리스트에 넣는다.
• 여름에 죽은 나무의 나이/2에 해당하는 양분을 넣어준다.
• 가을에 8방 탐색으로 나이가 5의 배수인 나무들에 대해 번식할 수 있도록 한다. 정렬 없이도 다시 봄을 맞았을 때 젊은 나무부터 꺼낼 수 있도록 큐에 애기 나무를 우선 넣고 나중에 부모 나무를 넣을 수 있도록 구현한다.
• 겨울에 add 배열을 통해 모든 지역에 양분을 추가한다.

2. 느낀점

• 일단 그 전에 풀었던 파이썬에서는 3차원 리스트로 풀었는데 통과되어서 자바에서 그대로  ArrayList 3차원 배열로 구현했는데.. 각 지역에 봄에 정렬하도록 하니깐.. 시간 초과 ^^..
• 당연하다.. k=1000이고 m이 최대 100까지므로.. 계속 정렬하고 넣고 빼고 한다면 시간초과가 날 것이다.
• 그 후 다른 자료구조를 찾다가 큐를 선택했다.. 
• 문제를 볼 때 시간을 활용하자 !

 

💻 소스코드

// BOJ - 나무 재테크 (16235번)
// 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_16235 {
	public static int n, m, k;
	public static int[][] add;
	public static int[][] map;
	public static class Tree implements Comparable<Tree>{
		int x;
		int y;
		int age;
		public Tree(int x, int y, int age) {
			this.x = x;
			this.y = y;
			this.age = age;
		}
		@Override
		public int compareTo(Tree o) {
			return this.age - o.age;
		}

	}
	public static int[] dx = {-1, 1, 0, 0, -1, 1, -1, 1};
	public static int[] dy = {0, 0, -1, 1, -1, -1, 1, 1};
	public static Queue<Tree> q;

	public static void main(String[] args) throws 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());
		add = new int[n][n];
		map = new int[n][n];
		q = new LinkedList<>();

		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<n;j++) {
				add[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());
			int y = Integer.parseInt(st.nextToken());
			int age = Integer.parseInt(st.nextToken());
			q.add(new Tree(x-1, y-1, age));
		}

		// 초반에만 정렬하면 더이상 정렬 필요 x
		Collections.sort((List<Tree>)q);

		for(int a=0;a<k;a++) {
			ArrayList<Tree> dead = new ArrayList<>();
			// 봄
			int q_len = q.size();

			while(q_len-- > 0) {
				Tree tree = q.poll();
				if(tree.age <= map[tree.x][tree.y]) {
					map[tree.x][tree.y] -= tree.age;
					q.add(new Tree(tree.x, tree.y, tree.age+1));
				} else {
					dead.add(new Tree(tree.x, tree.y, tree.age));
				}
			}



			// 여름
			for(Tree tree:dead) {
				map[tree.x][tree.y] += tree.age/2;
			}
			ArrayList<Tree> parent = new ArrayList<>();
			q_len = q.size();
			// 가을
			while(q_len-- > 0) {
				Tree tree = q.poll();
				parent.add(tree);
				if(tree.age % 5 == 0) {
					for(int d=0;d<8;d++) {
						int nx = tree.x + dx[d];
						int ny = tree.y + dy[d];
						if(0 <= nx && nx < n && 0 <= ny && ny < n) {
							q.add(new Tree(nx, ny, 1));
						}
					}
				}
			}

			for(Tree tree:parent) {
				q.add(tree);
			}

			// 겨울
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					map[i][j] += add[i][j];
				}
			}



		}


		System.out.println(q.size());
	}

}