/ BOJ

BOJ_16235_나무재테크_JAVA

문제 : 나무재테크

링크 : BOJ_16235_나무재테크

접근 방식

상당히 복잡한 형태의 시뮬레이션이 적당히 섞여있는 문제였다.

봄, 여름, 가을, 겨울에 나뉘어 각각의 로직이 작용한다.

봄 : 나무가 자신의 나이만큼 양분을 먹고 나이가 1 증가한다. 한 칸에 여러 개의 나무가 있을 경우 작은 나무부터 양분을 먹는다. 양분을 먹지 못하는 나무는 즉시 죽는다.

여름 : 봄에 죽은 나무가 양분으로 바뀐다. 각각의 나무의 나이/2 만큼 양분이 쌓인다.

가을 : 나무가 번식한다. 번식하는 나무는 나이가 5의 배수인 경우, 인접한 8칸에 나이가 1인 나무를 생성한다.

겨울 : 땅에 양분이 추가된다. 각각의 땅에 추가되는 양분의 양은 입력으로 주어진다.

덱이나 우선순위 큐를 사용해서 위에 적힌 로직을 순서대로 구현하기만 하면 되는 문제이다. 살짝 복잡하지만, 더 어려운 점은, 시간제한이 0.3초라는 것이다.

나는 우선순위 큐를 이용해서 문제를 풀었다. 하지만 우선순위 큐는 큐에 값을 추가할 때의 시간복잡도가 N(1)이 아니었기 때문에 정말 아슬아슬하게 통과가 되었다.

스터디원들의 풀이에 따르면 어린나이의 묘목은 덱을 이용해 앞에서부터 집어넣으면 되므로, 굳이 우선순위큐를 사용하지 않아도 가능하다. 시간초과의 늪에 빠지고 싶지 않다면 덱을 이용해 문제를 푸는 것을 권장한다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_11559_PuyoPuyo {

	static class Node {
		int x;
		int y;

		public Node(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

	}

	static int dir[][] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

	static boolean check;

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		char[][] arr = new char[12][6];
		for (int i = 0; i < 12; i++) {
			arr[i] = in.readLine().toCharArray();
		}
		int chain = 0;
		while (true) {
			check = false;
			for (int i = 0; i < 12; i++) {
				for (int j = 0; j < 6; j++) {

					if (arr[i][j] != '.') {
						bfs(arr[i][j], new Node(i, j), arr);
					}

				}
			}

			if(!check) {
				System.out.println(chain);
				return;
			}else {
				chain++;
				for(int i=11;i>=0;i--) {
					for(int j=0;j<6;j++) {
						if(arr[i][j] == '.') {
							for(int k=i;k>=0;k--) {
								if(arr[k][j] != '.') {
									arr[i][j] = arr[k][j];
									arr[k][j] = '.';
									break;
								}
							}
						}
					}
				}
			}

//			for(int i=0;i<12;i++) {
//				System.out.println(Arrays.toString(arr[i]));
//			}
		}

	}

	static void bfs(char simbol, Node node, char[][] arr) {

		Queue<Node> queue = new LinkedList<>();
		boolean[][] visited = new boolean[12][6];

		queue.offer(node);
		visited[node.x][node.y] = true;
		int cnt = 1;
		while (!queue.isEmpty()) {

			Node temp = queue.poll();

			for (int d = 0; d < 4; d++) {
				int dx = temp.x + dir[d][0];
				int dy = temp.y + dir[d][1];

				if (dx < 0 || dx >= 12 || dy < 0 || dy >= 6) {
					continue;
				}

				if (arr[dx][dy] == simbol && !visited[dx][dy]) {
					visited[dx][dy] = true;
					queue.offer(new Node(dx, dy));
					cnt++;
				}

			}

		}
		if (cnt >= 4) {
			check = true;
			for (int i = 0; i < 12; i++) {
				for(int j=0;j<6;j++) {
					if(visited[i][j]) {
						arr[i][j] = '.';
					}
				}
			}
		}

	}

}

위에 적힌 함정들만 조심하면 되는데, 브론즈에 속해있다보니 쉽게 생각해서 많이 틀리는 것 같다. 나도 정답을 얻어내는데 4회의 실패가 있었고, 이는 문제의 정답 비율 27%와 가깝다.