[백준 4179] 불!

생각 정리

불이 번져가는 경로와 지훈이가 탈출할 수 있는 경로 두 가지를 생각해야 한다.
2차원 배열에서 불이 번져가는 경로를 먼저 구하고 (bfs함수 호출), 그 다음 지훈이가 갈 수 있는 경로를 구한다.
불이 번져가는 경로는 벽이 아닐 경우 네 방향(상,하,좌,우)로 가능하고
지훈이는 벽이 아닐 경우 네 방향으로, 그리고 불이 없는 곳으로 이동이 가능하다.
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

생각치 못한 것

• 불이 난 곳이 여러 군데일 수 있다.
  - 불이 난 곳이 한군데인 경우와 무엇이 다를까 ??

  시작점을 한번에 queue에 넣는다.

• 지훈이가 미로를 탐색하다 주어진 미로의 길이를 벗어났다는 것은 미로를 탈출했다는 것이며, 그때의 지훈이의 이동거리를 구하고 리턴하면 된다. (하지만 불이 주어진 미로의 길이를 벗어났을 때 리턴하면 안된다.)

생각의 영감을 받은 곳

코드

import java.util.*;
import java.io.*;

class Position{
    int x;
    int y;
    
    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}


public class Main{
    static int R, C;
    static boolean[][] visited;
    static char[][] maze;
    static int[][] dist;
    static int min = Integer.MAX_VALUE;
    static int[][] fire;
    static boolean flag = false;
    static Queue<Position> queue = new LinkedList<>();

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

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        maze = new char[R][C];
        visited = new boolean[R][C]; 
        dist = new int[R][C];
        fire = new int[R][C];

        for(int i=0; i<R; i++) {
            String str = br.readLine();
            for(int j=0; j<C; j++) {
                maze[i][j] = str.charAt(j);
                if(maze[i][j] == 'F') {
                    queue.add(new Position(i, j));
                    visited[i][j] = true;
                }
            }
        }
        bfsF();

        //visited 방문여부 초기화
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                visited[i][j] = false;
            }
        }
        //queue 초기화
        queue = new LinkedList<>();

        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if(maze[i][j] == 'J') {
                    queue.add(new Position(i, j));
                    visited[i][j] = true;
                }
            }
        }
        
        bfsJ();

        if(!flag)
            System.out.println("IMPOSSIBLE");
        else 
            System.out.println(min);


    }

    static void bfsF() {
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        
        while(!queue.isEmpty()) {
            Position out = queue.poll();
            for(int i=0; i<4; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                else if(visited[nx][ny] || maze[nx][ny] == '#' ) continue;
                else {
                    queue.add(new Position(nx, ny));
                    visited[nx][ny] = true;  
                    fire[nx][ny] = fire[out.x][out.y] + 1;
                }
            }
             
        }

    }

    static void bfsJ() {
          int[] dx = {-1, 0, 1, 0};
          int[] dy = {0, -1, 0, 1};
  
  
          while(!queue.isEmpty()) {
              Position out = queue.poll();
              for(int i=0; i<4; i++) {
                  int nx = out.x + dx[i];
                  int ny = out.y + dy[i];
  
                  if(nx < 0 || ny < 0 || nx >= R || ny >= C) {
                      flag = true;
                      min = dist[out.x][out.y] + 1;
                      return ;
                  }
                  else if(visited[nx][ny] || maze[nx][ny] == '#' || maze[nx][ny] == 'F') continue;
                  else if(fire[out.x][out.y] != 0 && dist[out.x][out.y]+1 >= fire[nx][ny]) continue;
                  else {
                      queue.add(new Position(nx, ny));
                      visited[nx][ny] = true;  

                        dist[nx][ny] = dist[out.x][out.y] + 1;
                  }
              }
               
          }
  
      }
    
}