설명
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
•
#: 벽
•
.: 지나갈 수 있는 공간
•
J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
•
F: 불이 난 공간
J는 입력에서 하나만 주어진다.
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
예시 입력
예시 출력
4 4
####
#JF#
#..#
#..#
JavaScript
복사
3
JavaScript
복사
풀이 과정
그래프 탐색의 단골 문제 중 하나인 “탈출” 입니다.
이 문제의 특이한 점은 기존의 미로와 다르게 벽과 불이 존재하여 계속해서 갈 수 없는 경로가 생기는 건데요, 풀이는 간단합니다.
기존에는 Queue가 빌 때 까지 계속해서 갈 수 있는 경로를 Queue에 넣어주었습니다. 이번에는 불의 번짐과 플에이어의 움직임이 번갈아가면서 발생해야 합니다.
핵심 코드는 다음과 같습니다.
while (!playerQueue.isEmpty()) {
time++;
// Move fire
int fireSize = fireQueue.size();
for (int f = 0; f < fireSize; f++) {
int[] fire = fireQueue.poll();
for (int i = 0; i < 4; i++) {
int ny = fire[0] + dy[i];
int nx = fire[1] + dx[i];
if (isInBounds(ny, nx) && board[ny][nx] == '.') {
board[ny][nx] = 'F';
fireQueue.add(new int[]{ny, nx});
}
}
}
// Move player
int playerSize = playerQueue.size();
for (int p = 0; p < playerSize; p++) {
int[] player = playerQueue.poll();
for (int i = 0; i < 4; i++) {
int ny = player[0] + dy[i];
int nx = player[1] + dx[i];
// If reaches the edge, escape successful
if (!isInBounds(ny, nx)) return String.valueOf(time);
if (!visited[ny][nx] && board[ny][nx] == '.') {
visited[ny][nx] = true;
playerQueue.add(new int[]{ny, nx});
}
}
}
}
Java
복사
최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class _4179 {
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2){
return i1 - i2;
}
});
static char[][] board;
static int R, C;
static Queue<int[]> playerQueue = new LinkedList<>();
static Queue<int[]> fireQueue = new LinkedList<>();
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int[] dy = {0, 1, 0, -1}, dx = {-1, 0, 1, 0};
static boolean[][] visited;
public static void main(String[] args) throws IOException {
init();
System.out.println(escapeMaze());
}
public static void init() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
board = new char[R][C];
visited = new boolean[R][C];
for (int i = 0; i < R; i++) {
String input = br.readLine();
for (int j = 0; j < C; j++) {
board[i][j] = input.charAt(j);
if (board[i][j] == 'J') {
playerQueue.add(new int[]{i, j});
visited[i][j] = true;
} else if (board[i][j] == 'F') {
fireQueue.add(new int[]{i, j});
}
}
}
}
public static String escapeMaze() {
int time = 0;
while (!playerQueue.isEmpty()) {
time++;
// Move fire
int fireSize = fireQueue.size();
for (int f = 0; f < fireSize; f++) {
int[] fire = fireQueue.poll();
for (int i = 0; i < 4; i++) {
int ny = fire[0] + dy[i];
int nx = fire[1] + dx[i];
if (isInBounds(ny, nx) && board[ny][nx] == '.') {
board[ny][nx] = 'F';
fireQueue.add(new int[]{ny, nx});
}
}
}
// Move player
int playerSize = playerQueue.size();
for (int p = 0; p < playerSize; p++) {
int[] player = playerQueue.poll();
for (int i = 0; i < 4; i++) {
int ny = player[0] + dy[i];
int nx = player[1] + dx[i];
// If reaches the edge, escape successful
if (!isInBounds(ny, nx)) return String.valueOf(time);
if (!visited[ny][nx] && board[ny][nx] == '.') {
visited[ny][nx] = true;
playerQueue.add(new int[]{ny, nx});
}
}
}
}
return "IMPOSSIBLE";
}
public static boolean isInBounds(int y, int x) {
return y >= 0 && y < R && x >= 0 && x < C;
}
}
Java
복사
