문제
R x C 미로에서 지훈이(J)가 불(F)이 퍼지기 전에 미로 가장자리로 탈출하는 최소 시간을 구하라. 불과 지훈이는 매 분 상하좌우로 이동한다.
입력
첫째 줄에 R, C, 이후 R줄에 미로가 주어진다 (J: 지훈, F: 불, #: 벽, .: 빈칸).
출력
탈출 최소 시간을 출력한다. 불가능하면 "IMPOSSIBLE"을 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 4 #### #JF# #..# #..# | 3 |
풀이
불과 지훈이를 같은 BFS 큐에 넣되, 불을 먼저 넣어 불이 먼저 퍼지도록 한 뒤 지훈이가 가장자리에 도달하면 탈출이다.
- 불(type=1)을 큐에 먼저 넣고, 지훈이(type=0)를 나중에 넣는다
- BFS로 동시에 확산하며, 불은 빈칸을 'F'로 바꾸고 지훈이는 visited로 방문 체크한다
- 지훈이가 가장자리(edge)에 인접하면 현재 이동 수 + 1을 출력한다
- 큐가 비면 "IMPOSSIBLE"을 출력한다
핵심 아이디어: 같은 큐에서 불이 먼저 처리되므로 지훈이는 불이 퍼진 칸으로 이동할 수 없다.
코드
package day599;
import java.io.*;
import java.util.*;
public class Day590BOJ4179불 {
static int r;
static int c;
static char[][] maze;
static boolean[][] visited;
static Point jihun;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
r = Integer.parseInt(input[0]);
c = Integer.parseInt(input[1]);
maze = new char[r][c];
visited = new boolean[r][c];
Queue<Point> q = new LinkedList<>();
for (int i = 0; i < r; i++) {
input = br.readLine().split("");
for (int j = 0; j < c; j++) {
maze[i][j] = input[j].charAt(0);
if (maze[i][j] == 'J') {
if (isEdge(i, j)) {
System.out.println(1);
return;
}
maze[i][j] = '.';
jihun = new Point(i, j, 0, 0);
} else if (maze[i][j] == 'F') {
q.add(new Point(i, j, 1, 0));
}
}
}
bfs(q);
}
static void bfs(Queue<Point> q) {
int x;
int y;
int count;
q.add(jihun);
visited[jihun.x][jihun.y] = true;
while (!q.isEmpty()) {
Point p = q.poll();
x = p.x;
y = p.y;
count = p.count;
if (isEdge(x, y) && p.type == 0) {
System.out.println(count + 1);
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isRange(nx, ny) || maze[nx][ny] == '#' || maze[nx][ny] == 'F') {
continue;
}
if (p.type == 0 && !visited[nx][ny]) {
// 지훈
q.add(new Point(nx, ny, p.type, count + 1));
visited[nx][ny] = true;
} else if (p.type == 1) {
// 불
maze[nx][ny] = 'F';
q.add(new Point(nx, ny, p.type, count + 1));
}
}
}
System.out.println("IMPOSSIBLE");
}
static boolean isRange(int x, int y) {
if (x >= 0 && y >= 0 && x < r && y < c) {
return true;
}
return false;
}
static boolean isEdge(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isRange(nx, ny)) {
return true;
}
}
return false;
}
static class Point {
int x, y, type, count;
public Point(int x, int y, int type, int count) {
this.x = x;
this.y = y;
this.type = type;
this.count = count;
}
}
}복잡도
- 시간: O(NM)
- 공간: O(NM)