[BOJ] 4179 불! - Java

✨ BFS ➔ 동시에 이동시키기 

https://www.acmicpc.net/problem/4179

4179번: 불!

---

📍 고려해야할 점

• 불과 지훈이를 동시에 이동시켜야한다. 
  • 동시에 이동시키기 위해서 두 개의 큐를 사용한다.
• 불은 지훈이의 존재 여부에 대해 영향을 받지 않는다. (지훈이가 있거나 없어도 언제든지 벽만 아니라면 언제든지 전파 가능)
• 지훈이는 불의 존재 여부에 대해 영향을 받는다. (불이 존재한다면 이동 불가)
• 지훈이가 가장자리에 도달하면 미로를 통과할 수 있다. 

 

🕹️ 풀이과정 

1️⃣ 미로의 정보를 2차원 배열에 저장하고, 지훈이의 위치와 불의 위치를 각 큐(jQ, fQ)에 저장한다. 

2️⃣ 불을 먼저 4 방향에 전파시킨다. (방문 여부는 해당 격자에 있는 문자형으로도 판단할 수 있기 때문에 visit[][] 배열은 구현 X)

3️⃣ 지훈이를 4 방향 중 불이 존재하지 않고, 벽이 아닌 '.' 곳으로 이동시킨다. 

4️⃣ 만약 이동한 곳이 미로의 범위를 벗어난 곳이라면 지훈이는 탈출할 수 있기 때문에 탈출시간을 출력하고 끝낸다.

5️⃣ 더이상 지훈이가 이동할 수 없다면 큐(jQ)가 비어있기 때문에 "IMPOSSIBLE"을 출력하고 끝낸다. 

6️⃣ 미로의 범위를 벗어나지 않았다면 jQ에 이동할 곳을 넣고 종료 조건에 만족할 때까지 반복한다. 

 

 

 

👩‍💻  전체 코드 

 

public class BOJ_4179_불 {
    static int r, c, cnt;
    static char[][] maze;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static Queue<Info> jQ = new LinkedList<>();
    static Queue<Info> fQ = new LinkedList<>();
    
    static class Info{
        int x, y;

        public Info(int x, int y){
            this.x=x;
            this.y=y;
        }
    }

    static void bfs(){

        while(true){
            cnt++; // 탈출 소요 시간 
            int fs = fQ.size();

            // 불 전파시키기
            while(fs-->0){
                Info fN = fQ.poll();

                // 네 방향으로 불 전파
                for(int i=0; i<4; i++){
                    int fnx = fN.x + dx[i];
                    int fny = fN.y + dy[i];

                    if(fnx>=0 && fny>=0 && fnx<r && fny<c){
                        if(maze[fnx][fny]=='J' || maze[fnx][fny]=='.'){
                            maze[fnx][fny]='F';
                            fQ.add(new Info(fnx, fny));
                        }
                    }
                }
            }

            // 지훈이 이동시키기
            int js = jQ.size();
            while(js-->0){
                Info jN = jQ.poll();

                for(int i=0; i<4; i++){
                    int jnx = jN.x + dx[i];
                    int jny = jN.y + dy[i];

                    if(jnx>=0 && jny>=0 && jnx<r && jny<c){
                        if(maze[jnx][jny]=='.'){
                            maze[jnx][jny] = 'J';
                            jQ.add(new Info(jnx, jny));
                        }
                    }
                    // 지훈이가 미로 범위를 벗어났다면 통과했으므로 출력 후 끝내기
                    else{
                        System.out.println(cnt);
                        return;
                    }
                }
            }

            // 지훈이가 이동할 곳이 없다면 IMPOSSIBLE 출력
            if(jQ.isEmpty()){
                System.out.println("IMPOSSIBLE");
                return;
            }
        }
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        maze = new char[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] == 'J'){
                    jQ.add(new Info(i, j));
                } else if(maze[i][j]=='F'){
                    fQ.add(new Info(i,j));
                }
            }
        }
        bfs();
    }
}