[코테 매일 풀기 18일차] 1201

백준 4179 불

소요시간 : 90분..

아이디어

• 핵심 : 지훈이가 불보다 먼저 움직여서 가장 자리로 탈출 가능한가?
• 문제 분류
  a. 최단 거리 / 시간 -> bfs 알고리즘
  b. 불과 사람이 동시에 이동 -> 멀티 bfs

• 알고리즘 설계

1. 입력 받기 
- 지도 입력하며, J, F 위치 저장 
- fireTime, exitTime 배열 -1로 초기화 

2. 불 BFS 실행 
- 모든 F 위치 큐에 넣고 시작 
- 4방향 탐색하며, fireTime[nx][ny] 갱신 
- 벽(#)은 지나갈 수 없음 

3. 지훈 bfs 실행 
- J위치에서 시작 
- 4 방향 탐색하며: 
	a. 범위 벗어나면 탈출 성공 -> 시간 출력하고 종료 
    b. 벽이거나 이미 방문 -> continue
    c. 불이 먼저 도착 -> contonue 
    d. 갈 수 있으면 큐에 추가 
- 큐가 비면 -> IMPOSSIBLE 

4. 출력 

``
---


```java
package boj_gold.p4179_불;

//미로 문제 이구만
// 경계 설정이 잘 되야겠구만
// 아이디어: 불과 지훈이의 bfs 모두 돌려얗.ㅁ
// 불의 bfs를 먼저 돌려야함 ( 지훈이의 이동에 영향 안받음)
// 각칸에 불이 전파되는 시간을 구한다.
// 지훈이의 bfs를 돌려 이동시킨다.
    // 지훈이보다 먼저 불이 도달한 공간에는 방문할 수 없다.
    // 불이 특정 공간에 도달하는 시간 <= 지훈이가 특정 공간에 도달하는 시간
// 지훈이가 배열의 범위를 벗어나면, 탈출 성공
// 배열의 범위 못벗어나면, 탈출 실패 -> impossible 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Answer {
    static int n, m;
    static char[][] maps;

    static int[][] fireTime; //불이 각 칸에 도달하는 시간
    static int[][] exitTime; //지훈이가 도달하는 시간


    static Queue<int[]> q1;
    static Queue<int[]> q2;

    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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());
        fireTime = new int[n][m];
        exitTime = new int[n][m];
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();

        maps = new char[n][m];


        //입력 받기 #은 0으로 생각, J는 이동 F는 불이어서 bfs로 퍼짐 // 만약 탈출되지 않으면 Impossible 출력
        // . 은  1로 생각
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                maps[i][j] = line.charAt(j);
                //시간 초기화 하기
                fireTime[i][j] = -1;
                exitTime[i][j] = -1;
                //불 인덱스 추가
                if (maps[i][j] == 'F') {
                    //불의 인덱스 추가
                    q1.offer(new int[]{i, j});
                    fireTime[i][j] = 0; //불 시작점은 시간 0
                } else if (maps[i][j] == 'J') {
                    q2.offer(new int[]{i, j});
                    exitTime[i][j] = 0; //초기화
                }
            }
        }//입력 받기

        // 불에 대한 bfs
        while (!q1.isEmpty()) {
            int[] cur = q1.poll();
            int x = cur[0];
            int y = cur[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                // 경계 벗어나면 x
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                //불이 먼저 오면 안됨
                if (fireTime[nx][ny] >= 0 || maps[nx][ny] == '#') continue;
                fireTime[nx][ny] = fireTime[x][y] + 1;
                q1.offer(new int[]{nx, ny});
            }
        }
        //지훈이 bfs
        while (!q2.isEmpty()) {
            int[] cur = q2.poll();
            int x = cur[0];
            int y = cur[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                //범위 벗어나면 탈출
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    System.out.println(exitTime[x][y] + 1);
                    return;
                }
                if (exitTime[nx][ny] >= 0 || maps[nx][ny] == '#') continue;
                //불의 전파 시간이 더 먼저 오면
                // 불이 오는 칸이면 비교 fireTime == -1이면 불이 안오는 칸 -> 안전

                if (fireTime[nx][ny]!= -1 && fireTime[nx][ny] <= exitTime[x][y] + 1) continue;
                exitTime[nx][ny] = exitTime[x][y] + 1;
                q2.offer(new int[]{nx, ny});
            }
        }
        System.out.println("IMPOSSIBLE");

    }//main


}