https://www.acmicpc.net/problem/4179
난이도
골드3
문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
#: 벽
.: 지나갈 수 있는 공간
J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
F: 불이 난 공간
J는 입력에서 하나만 주어진다.
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
내 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
boolean[][] map = new boolean[N][M];
int[] dx = { -1, 0, 1, 0 };
int[] dy = { 0, 1, 0, -1 };
int[][] jihoonTime = new int[N][M];
int[][] fireTime = new int[N][M];
Queue<int[]> jihoonQueue = new LinkedList<>();
Queue<int[]> fireQueue = new LinkedList<>();
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < M; j++) {
if (str.charAt(j) == '#') {
map[i][j] = false;
} else if (str.charAt(j) == '.') {
map[i][j] = true;
} else if (str.charAt(j) == 'J') {
jihoonTime[i][j] = 1;
jihoonQueue.add(new int[] { i, j });
} else {
fireTime[i][j] = 1;
fireQueue.add(new int[] { i, j });
}
}
}
while (!fireQueue.isEmpty()) {
int[] now = fireQueue.poll();
for (int i = 0; i < 4; i++) {
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) {
continue;
}
if (!map[nx][ny] || fireTime[nx][ny] > 0) {
continue;
}
fireTime[nx][ny] = fireTime[now[0]][now[1]] + 1;
fireQueue.add(new int[] { nx, ny });
}
}
while (!jihoonQueue.isEmpty()) {
int[] now = jihoonQueue.poll();
for (int i = 0; i < 4; i++) {
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) {
System.out.println(jihoonTime[now[0]][now[1]]);
return;
}
if (!map[nx][ny] || jihoonTime[nx][ny] > 0) {
continue;
}
if (fireTime[nx][ny] == 0 || jihoonTime[now[0]][now[1]] + 1 < fireTime[nx][ny]) {
jihoonTime[nx][ny] = jihoonTime[now[0]][now[1]] + 1;
jihoonQueue.add(new int[] { nx, ny });
}
}
}
System.out.println("IMPOSSIBLE");
}
}bfs를 두 번 사용해서 문제를 풀었다.
우선 지훈이의 이동 시간을 저장하기 위한 jihoonTime과 불의 이동 시간을 저장하기 위한 fireTime을 선언하고, 둘의 이동을 확인하기 위한 Queue를 각각 선언했다.
문제에서 주어지는 정보를 위에 선언한 변수들에 잘 넣어주고, 벽의 위치 정보를 저장하기 위한 map을 선언하여 갈 수 있는지 없는지를 구분했다.
먼저 불의 이동 경로와 시간을 활용하기 위해 fireQueue를 통해서 BFS로 fireTime을 갱신해줬다. 격자 범위를 넘어가거나 벽이거나 fireTime[nx][ny] > 0(visited 용도로 사용)인 경우라면 갈 수 없거나 이미 확인한 경로이기 때문에 중복 방문을 피하기 위해 넘어간다.
그리고 그 모든 조건을 넘어갔다면 기존 위치 + 1한 값을 새 위치에 넣어주고, Queue에도 저장한다.
그리고 다음은 지훈이의 이동 경로와 시간을 활용한다. jihoonQueue를 통해서 BFS로 동일하게 이동 경로를 탐색하는데, 이때 격자를 벗어나면 지훈이는 탈출을 한 것이기 때문에 답으로 출력하고 빠져나가면 된다.
그리고 불과 동일하게 벽이거나 이미 방문한 곳이면 넘어가고, 지훈이가 갈 수 있는 경우는 한가지 조건이 추가되는데 불의 시간이랑 비교를 진행해야 한다.
불이 닿을 수 없는 경우(fireTime[nx][ny] == 0)거나 지훈이가 다음 칸으로 이동했을 때 불이 아직 닿지 않은 곳인 경우(jihoonTime[now[0]][now[1]] + 1 < fireTime[nx][ny])에만 지훈이는 이동이 가능하다.
모든 과정을 거쳤는데 지훈이가 탈출하지 못했으면 IMPOSSIBLE을 출력하면 된다.
그리고 나는 초기 지훈의 위치의 시간을 1로 지정해뒀기 때문에 답을 출력할 때 1을 추가하지 않았다. 원래는 0으로 시작하는게 더 명확하게 이해될 수 있을 것 같기는 하지만 배열을 초기화하는 것보다 효율적일 것이라 생각해서 그냥 1로 시작을 하고 마지막에 1을 더하지 않고 답을 출력했다.
