백준 5427번: 불

문제 설명

• https://www.acmicpc.net/problem/5427
• 1초가 지나면 불과 사람은 4방향 중 한 곳으로 이동하게 됩니다.
• 사람은 2차원 배열의 테두리에 도달하면 +1초 후 탈출에 성공하게 됩니다.

접근법

• 불과 사람의 움직임을 하나의 큐(정확히는 덱)에서 처리할 수 있습니다.
  • 불 or 사람을 판단하는 변수를 추가했습니다.
• 사람일 때 방문처리를 #(벽) 또는 *(불)가 아닌 @(사람)으로 처리함으로써 불이 @로 표현된 지역은 도달 가능하게 만들었습니다.

정답

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

public class Main {
	static int R, C;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		for (int t = 0; t < T; t++) {
			st = new StringTokenizer(br.readLine());
			C = Integer.parseInt(st.nextToken());
			R = Integer.parseInt(st.nextToken());
			char[][] board = new char[R][C];
			for (int i = 0; i < R; i++) {
				board[i] = br.readLine().toCharArray();
			}

			Deque<int[]> deq = new LinkedList<int[]>();
			int[] temp = null;
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if (board[i][j] == '@') {
						temp = new int[] { i, j, 0 };
						deq.addLast(temp); // 사람을 마지막에 넣는 이유: 불과 같은 칸으로 갈 수 없기 때문
						/*
						 * #### #*.. // 첫번째 .으로 불과 사람이 동시에 움직이게 된다. 이 때는 이동이 불가능하기 때문에 불이 먼저 움직이는걸로 생각해야
						 * 함 ##@# ####
						 */
					}
					if (board[i][j] == '*') {
						deq.addFirst(new int[] { i, j, 1 });

					}

				}
			}
			BFS(deq, board);

		}

	}

	public static void BFS(Deque<int[]> deq, char[][] board) {
		int cnt = 0;
		while (!deq.isEmpty()) {
			int size = deq.size();
			cnt++;
			while (--size >= 0) {
				int[] now = deq.poll();
				int who = now[2];
				if (who == 0) { // 사람이면
					if ((now[0] == 0 || now[0] == R - 1 || now[1] == 0 || now[1] == C - 1)) {
						System.out.println(cnt);
						return;
					}

					for (int d = 0; d < 4; d++) {
						int nx = now[0] + dx[d];
						int ny = now[1] + dy[d];
						if (0 <= nx && nx < R && 0 <= ny && ny < C && board[nx][ny] == '.') {
							board[nx][ny] = '@'; // 방문처리
							deq.add(new int[] { nx, ny, who });
						}
					}
				} else { // 불이면
					for (int d = 0; d < 4; d++) {
						int nx = now[0] + dx[d];
						int ny = now[1] + dy[d];
						if (0 <= nx && nx < R && 0 <= ny && ny < C && (board[nx][ny] == '.' || board[nx][ny] == '@')) {
							board[nx][ny] = '*'; // 불이 번짐
							deq.add(new int[] { nx, ny, who });
						}
					}
				}
			}
		}
		System.out.println("IMPOSSIBLE");
	}

}