/ BOJ

BOJ_5247_불_JAVA

문제 : 불

링크 : BOJ_5247_불

접근 방식

BFS문제로 보이지만 조건이 까다로워 난이도가 있어보인다. 조건은 다음과 같다.

  1. 매 초마다 불은 4방으로 퍼져나간다.

  2. 상근이는 4방향 이동할 수 있으며, 1초가 걸린다. 그리고, 이제 불이 붙으려는 칸으로 이동할 수 없다.

  3. 상근이는 불이 자신의 칸에 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

불의 입장에서 BFS가 필요하고, 상근이의 입장에서 BFS도 필요했다. 나는 BFS에서 사용하는 Queue는 선입선출이니까, 먼저 불을 모두 Queue에 offer 시킨 뒤에 상근이를 추가하면 불 먼저 -> 상근 으로의 순서대로 탐색이 진행될 것이라고 생각했다. 하지만 여기서 문제가 있다.

불 먼저 퍼트리고 상근이를 이동시킨다면 2번 조건은 자연스럽게 클리어 된다. 하지만 3번 조건에서 상근과 불이 만났을 경우에 상근이 불로 덮어씌워지는 문제가 생긴다.

이 문제를 해결하기 위해 나는 상근과 불이 함께 있는 상태인 ‘!’를 새로 정의했다. 배열의 값이 ‘!’인 경우에 상근으로 간주한다. 또한 !에서 상근이 이동했을 경우 그 기존 자리는 ‘*‘으로 채워 불으로 처리를 시켜준다.

새로운 상태를 정의함으로써, 조건을 모두 만족하면서 BFS를 돌릴 수 있었다.

소스 코드

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

public class BOJ_5247_불 {

	static class Node {
		int x;
		int y;
		int weight;

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

	}

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

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

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

		int T = Integer.parseInt(in.readLine());
		StringTokenizer st;
		for (int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(in.readLine(), " ");

			int M = Integer.parseInt(st.nextToken());

			int N = Integer.parseInt(st.nextToken());

			char arr[][] = new char[N][M];

			for (int i = 0; i < N; i++) {
				arr[i] = in.readLine().toCharArray();
			}
			Queue<Node> queue = new LinkedList<>();
			Node node = null;
			boolean[][] visited = new boolean[N][M];
			boolean[][] visitedfire = new boolean[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (arr[i][j] == '*') {
						queue.offer(new Node(i, j, 1));
						visitedfire[i][j] = true;
					}

					if (arr[i][j] == '@') {
						node = new Node(i, j, 1);
						visited[i][j] = true;
					}
				}
			}
			boolean clear = false;
			queue.offer(node);

			while (!queue.isEmpty()) {

				Node temp = queue.poll();

				int x = temp.x;
				int y = temp.y;
				if (arr[x][y] == '@' || arr[x][y] == '!') {
//					System.out.println("x : " + x + " y : "+ y);
					if (x == 0 || x == N - 1 || y == 0 || y == M - 1) {
						clear = true;
						System.out.println(temp.weight);
						break;
					}
				}

				for (int d = 0; d < 4; d++) {

					int dx = x + dir[d][0];
					int dy = y + dir[d][1];
					if (dx < 0 || dx >= N || dy < 0 || dy >= M) {
						continue;
					}
					if (arr[x][y] == '*') {
						if ((arr[dx][dy] == '.' || arr[dx][dy] == '@') && !visitedfire[dx][dy]) {

							if (arr[dx][dy] == '@') {
								arr[dx][dy] = '!';
							} else {
								arr[dx][dy] = '*';
							}
							visitedfire[dx][dy] = true;
							queue.offer(new Node(dx, dy, temp.weight + 1));
						}
					} else if ((arr[x][y] == '@' || arr[x][y] == '!') && !visited[dx][dy] && arr[dx][dy] == '.') {
						arr[dx][dy] = '@';
						visited[x][y] = true;
						if (arr[x][y] == '!') {
							arr[x][y] = '*';
						}
						visited[dx][dy] = true;
//						System.out.println(temp.weight+ " x : " + x + " y : " + y);
						queue.offer(new Node(dx, dy, temp.weight + 1));
					}
				}
			}
			if (!clear) {
				System.out.println("IMPOSSIBLE");
			}
		}

	}

}

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