[Java] 백준 4179번 불!

이 글은 백준 4179번 불!을 풀이한다. 코드는 Java로 구현하였다.

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

예제 입력 1

4 4
####
#JF#
#..#
#..#

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

예제 출력 1

3

제한

• 시간: 1초
• 메모리: 256MB

풀이

접근

이 문제는 불에 대한 BFS와 지훈이에 대한 BFS를 모두 돌림으로서 해결이 가능하다.

지훈이의 이동이 불의 전파에 영향을 받지만, 불의 전파는 지훈이의 이동에 영향을 받지 않기 때문에 불만 먼저 전파를 쭉 시킨다.

불에 대한 BFS를 돌려서 미리 각 칸에 불이 전파되는 시간을 다 구해둔다.

 

그 다음에는 지훈이에 대한 BFS를 돌려서 지훈이를 이동시킨다.

지훈이의 이동은 불의 전파에 영향을 받기 때문에 BFS를 돌릴 때 조건문을 조금 수정해줄 필요가 있다.

1. 지훈이보다 먼저 불이 도달한 공간에는 방문할 수 없게 처리한다.
   = 불이 특정 공간에 도달하는 시간 <= 지훈이가 특정 공간에 도달하는 시간 
2. 지훈이가 배열의 범위를 벗어났을 경우, 탈출 성공하게 처리한다.

지훈이가 한번이라도 배열의 범위를 벗어나지 못했을 경우, 탈출에 실패했다는 의미이므로 IMPOSSIBLE을 출력한다.

구현

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair {

  int X, Y;

  Pair(int X, int Y) {
    this.X = X;
    this.Y = Y;
  }
}

public class baekjoon4179 {

  static int n, m;
  static char[][] board;
  static int[][] dist1; // 불의 전파 시간
  static int[][] dist2; // 지훈이의 이동 시간
  static int[] dx, dy;
  static Queue<Pair> Q1;
  static Queue<Pair> Q2;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());

    board = new char[n][m];
    dist1 = new int[n][m]; // 불의 전파 시간
    dist2 = new int[n][m]; // 지훈이의 이동 시간
    Q1 = new LinkedList<>();
    Q2 = new LinkedList<>();
    dx = new int[] { 1, 0, -1, 0 };
    dy = new int[] { 0, 1, 0, -1 };

    // 배열 초기화
    for (int i = 0; i < n; i++) {
      String s = br.readLine();
      for (int j = 0; j < m; j++) {
        board[i][j] = s.charAt(j);
        dist1[i][j] = -1;
        dist2[i][j] = -1;
        if (board[i][j] == 'F') {
          Q1.offer(new Pair(i, j));
          dist1[i][j] = 0;
        }
        if (board[i][j] == 'J') {
          Q2.offer(new Pair(i, j));
          dist2[i][j] = 0;
        }
      }
    }
    // 불에 대한 BFS
    while (!Q1.isEmpty()) {
      Pair cur = Q1.poll();
      for (int dir = 0; dir < 4; dir++) {
        int nx = cur.X + dx[dir];
        int ny = cur.Y + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue;
        dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
        Q1.offer(new Pair(nx, ny));
      }
    }

    // 지훈이에 대한 BFS
    while (!Q2.isEmpty()) {
      Pair cur = Q2.poll();
      for (int dir = 0; dir < 4; dir++) {
        int nx = cur.X + dx[dir];
        int ny = cur.Y + dy[dir];
        // 범위를 벗어났다는 것은 탈출에 성공했다는 의미
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
          System.out.println(dist2[cur.X][cur.Y] + 1);
          return;
        }
        if (dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
        // 불의 전파 시간을 조건에 추가
        if (dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1) continue;
        dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
        Q2.offer(new Pair(nx, ny));
      }
    }

    System.out.println("IMPOSSIBLE");
  }
}