불
백준 5427: 불
풀이
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);
}
}
}