백준 5427: 불

문제보기
Alt text

풀이

BFS를 이용
불이 먼저 옮겨 붙은 다음 상근이 이동(순서 주의)

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static class Node {
		int c, r, cnt, check;

		Node(int r, int c, int cnt, int check) {
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.check = check;
		}
	}

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

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int w = sc.nextInt(); // 지도의 너비
			int h = sc.nextInt(); // 지도의 높이
			int map[][] = new int[h][w]; // 지도
			boolean visited[][] = new boolean[h][w];
			Queue<Node> queue = new LinkedList<>();
			for (int i = 0; i < h; i++) {
				String str = sc.next();
				for (int j = 0; j < w; j++) {
					char c = str.charAt(j);
					if (c == '#')
						map[i][j] = 99;
					else if (c == '.')
						map[i][j] = 0;
					else if (c == '*') {
						map[i][j] = 1;
						queue.add(new Node(i, j, 0, 1));
					} else if (c == '@') {
						map[i][j] = -1;
					}
				}
			}

			loop: for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (map[i][j] == -1) {
						queue.add(new Node(i, j, 0, 0));
						map[i][j] = 0;
						visited[i][j] = true;
						break loop;
					}
				}
			}

			int time = -1;

			loop: while (!queue.isEmpty()) {
				Node node = queue.poll();

				if (node.check == 1) { // 불이면
					for (int d = 0; d < 4; d++) {
						int nr = node.r + dr[d];
						int nc = node.c + dc[d];
						if (nr >= 0 && nc >= 0 && nr < h && nc < w) {
							if (map[nr][nc] == 0) { // 다음 칸이 빈공간이면
								map[nr][nc] = 1;
								queue.add(new Node(nr, nc, node.cnt + 1, 1));
							}
						}
					}
				} else if (node.check == 0) { // 상근이라면
					for (int d = 0; d < 4; d++) {
						int nr = node.r + dr[d];
						int nc = node.c + dc[d];
						if (nr >= 0 && nc >= 0 && nr < h && nc < w) {
							if (map[nr][nc] == 0 && !visited[nr][nc]) { // 다음 칸이 빈공간이고 방문한 곳이 아니라면
								queue.add(new Node(nr, nc, node.cnt + 1, 0));
								visited[nr][nc] = true;
							}
						} else { // 범위 벗어나면 탈출!
							time = node.cnt + 1;
							break loop;
						}
					}
				}
			}

			if (time == -1)
				System.out.println("IMPOSSIBLE");
			else
				System.out.println(time);
		}

	}
}