백준 4179번 불 - 골드 4

불과 지훈이를 같이 bfs 돌릴 생각을 했는데 따로 돌려도 되더라.

 

1. 지훈이는 불의 영향을 받으므로 불부터 bfs 돌리기

불이 이동한 칸에 시간 기입

 

2. 지훈이 이동한 칸에 시간 기입

단, 같은 시간일 때 불이 이동한 칸에는 이동할 수 없음

-> 불의 이동시간 <= 지훈이의 이동시간 일 경우 x

-> 처음에 다 -1로 초기화하기 때문에 불이 이동하지 않으면 항상 지훈이의 이동시간의 값이 더 큼

이런 경우를 위해 불의 이동시간이 -1이 아니라는 조건 추가해야 함.

여기서 굉장히 애먹음

 

3. 지훈이가 미로의 범위를 벗어나면 탈출 성공 

한 번도 못 벗어나면 IMPOSSIBLE 출력

 

* 처음에 불의 위치와 지훈이의 위치를 초기화할 때 시간을 0으로 바꿔줘야 함.

이거 놓쳤더니 어디가 잘못됐나 한참 찾음

 

* 이 문제는 동시에 돌리지 않아도 풀 수 있었지만

시작점이 2개라면 동시에 돌려야 함 -> 백트래킹 기법을 섞어서 풀어야 함.

 

import java.io.*;
import java.util.*;
class Main{
    public static class Pair{
        int x;
        int y;
        Pair(int x, int y){
            this.x=x;
            this.y=y;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(
                new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(
                new OutputStreamWriter(System.out));

        String[] str=br.readLine().split(" ");
        int R=Integer.parseInt(str[0]); // 미로 행
        int C=Integer.parseInt(str[1]); // 미로 열
        String [][] miro=new String[R][C];
        Queue<Pair> J_q=new LinkedList<>();
        Queue<Pair> F_q=new LinkedList<>();

        int[][] J_visit=new int[R][C]; // 지훈이 방문 체크
        int[][] F_visit=new int[R][C]; // 불 방문 체크

        for(int i=0;i<R;i++){ // 미로 입력
            String[] str2=br.readLine().split("");
            for(int j=0;j<C;j++){
                // 방문 체크 배열 초기화 -1로
                J_visit[i][j]=-1;
                F_visit[i][j]=-1;

                if(str2[j].equals("J")) {
                   // 지훈이 위치 저장
                   J_q.add(new Pair(i, j));
                   J_visit[i][j]=0;
                } else if(str2[j].equals("F")) {
                    // 불 위치 저장
                    F_q.add(new Pair(i, j));
                    F_visit[i][j]=0;
                    // 초기에 불이 있는 자리는 0으로 함, 불이 처음부터 여러곳 번져 있을 수도 있다는 이슈
                }
                miro[i][j]=str2[j];
            }
        }


        int[] dx={0,0,-1,1}; // 상하좌우 x좌표
        int[] dy={-1,1,0,0}; // 상하좌우 y좌표

        //불에 대한 BFS
        while (!F_q.isEmpty()){
            Pair f=F_q.poll();
            for(int i=0;i<4;i++){
                int nx=f.x+dx[i];
                int ny=f.y+dy[i];
                if(nx<0 || ny<0 || nx>=R || ny>=C) //범위 체크
                    continue;
                if(miro[nx][ny].equals("#") || F_visit[nx][ny]>=0){
                    //지나갈 수 없거나, 이미 방문한 곳이면 패스
                    continue;
                }
                F_q.add(new Pair(nx, ny));
                F_visit[nx][ny]=F_visit[f.x][f.y]+1;

            }
        }


        //지훈이에 대한 BFS
        while(!J_q.isEmpty()){
            Pair j=J_q.poll();
            for(int i=0;i<4;i++){
                int nx=j.x+dx[i];
                int ny=j.y+dy[i];
                if(nx<0 || ny<0 || nx>=R || ny>=C){
                    /* 미로 범위를 벗어나면 탈출 성공,
                    가장 빠른 경우 찾는거니깐 바로 출력하고 종료*/
                    bw.write(J_visit[j.x][j.y]+1+"");
                    bw.flush();
                    bw.close();
                    return;
                }
                if(miro[nx][ny].equals("#")|| J_visit[nx][ny]>=0) {
                    //지나갈 수 없거나, 이미 방문한 곳이면 패스
                    continue;
                }
                if(F_visit[nx][ny]!=-1 &&
                        F_visit[nx][ny]<=J_visit[j.x][j.y]+1){
                    //불의 전파시간보다 지훈이의 도착시간이 더 크거나 같으면 패스
                    //불이 아예 안갔는데도 지훈이의 방문시간이 더 큰 경우가 있어서 조건 추가
                     continue;
                }
                J_q.add(new Pair(nx, ny));
                J_visit[nx][ny]=J_visit[j.x][j.y]+1;
            }
        }

        //여기까지 왔으면 탈출 실패한 것
        bw.write("IMPOSSIBLE");
        bw.flush();
        bw.close();
    }
}