백준 4179: 불![JAVA]

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

4179번: 불!

 

 

[정답 코드]

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

public class Main {
    static int R, C, answer = Integer.MAX_VALUE;
    static char[][] graph;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Queue<int[]> jihoon = new LinkedList<>(); // 지훈이의 좌표가 담긴 큐
    static Queue<int[]> fire = new LinkedList<>(); // 불의 좌표가 담긴 큐
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        graph = new char[R][C];
        for (int i = 0; i < R; i++) {
            String input = br.readLine();
            for (int j = 0; j < C; j++) {
                graph[i][j] = input.charAt(j);
                if (graph[i][j] == 'J') {
                    jihoon.offer(new int[]{i, j});
                }
                if (graph[i][j] == 'F') {
                    fire.offer(new int[]{i, j});
                }
            }
        }
        br.close();

        int answer = 0;
        while (true) {
            answer++; // while 반복문을 1회 시행할 때 마다 1분이 지난것이므로 1씩 증가
            int fireSize = fire.size(); // 불의 좌표가 담긴 큐의 크기 == 불의 갯수
            while (fireSize > 0) { // 번져야 할 불의 개수만큼만 반복, 이미 번진 불은 번지는것을 반복하지 않음
                fireSize--;
                int[] tmp = fire.poll();
                int x = tmp[0];
                int y = tmp[1];
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                        if (graph[nx][ny] == '.' || graph[nx][ny] == 'J') { // 불이 번진 위치가 벽이 아니라면
                            fire.offer(new int[]{nx, ny}); // 새로운 불의 좌표를 큐에 담는다
                            graph[nx][ny] = 'F'; // 번진만큼 지도를 갱신
                        }
                    }
                }
            }

            int jihoonSize = jihoon.size();
            while (jihoonSize > 0) { // 지훈이의 좌표가 담긴 큐가 비어있지 않을 경우
                jihoonSize--; // 새로운 지훈이의 좌표갯수만큼만 반복, 이미 이동한 지훈이는 이동하는것을 또 반복하지 않음
                int[] tmp = jihoon.poll();
                int x = tmp[0];
                int y = tmp[1];
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx < 0 || nx >= R || ny < 0 || ny >= C) { // 탈출을 했을 경우
                        System.out.println(answer);
                        return;
                    }
                    if (graph[nx][ny] == '.') { // 이동가능한 자리일 경우
                        jihoon.offer(new int[]{nx, ny}); // 이동한 위치의 좌표를 큐에 담는다
                        graph[nx][ny] = 'J'; // 이동한 위치를 J로 갱신 (사실 이 코드는 필요하지는 않음)
                    }
                }
            }
            if (jihoon.isEmpty()) { // 새로이동할 때마다 지훈이의 좌표가 담긴 큐 jihoon 이 늘어나는데, 이동이 불가능하면 큐가 비게 됨
                System.out.println("IMPOSSIBLE");
                return;
            }
        }
    }
}

 

[설명]

bfs심화문제이다. 지훈이가 4방탐색을 하며 지도밖을 나갈 경우 반복문이 종료되는 것까지를 구현하는것은 약간만 생각하면 할 수 있다. 하지만 다른문제와 다른것은 지훈이가 4방탐색을함과 동시에 불도 4방으로 퍼져나간다는것을 생각해야 한다. 나는 이부분에서 막혀서 다른글을 참고했다. 

 

대략적인 풀이방식은 이렇다 : 

1. 불과 지훈이의 좌표를 각 큐에 담는다.

2. 불이 먼저 퍼져나가며 퍼져나간 불의 위치를 큐에 담는다.

3. 지훈이가 4방탐색을 하며 지훈이가 갈 수 있는 모든위치의 좌표를 큐에 담는다.

4. 이미 퍼져나간 불은 한 번더 퍼져나갈필요가없다. 새롭게 퍼져나간 불만 다시 퍼져나간다. (애초에 이미 퍼져나간불은 큐에 좌표가 없다.)

5. 3에서 4방탐색을 하며 지훈이가 갈 수 있는 모든 위치에서 다시 4방탐색을 하며 탈출구를 찾는다.

6. 4, 5를 반복한다.

7 - 1. 지훈이의 좌표가 지도 밖을 나갈경우 정답을 출력해준다.

7 - 2. 지훈이가 더이상 새롭게 이동할수 있는 위치가 없을 경우 jihoon 큐에는 더이상 값이 안담겨있기 때문에 IMPOSSIBLE을 출력해준다.

 

디버깅모드를 하고 지도의 모습을 시뮬레이션한것을 보면 약간은 신기하다. 여기서 중요한점은 불이 지훈이의 위치가 담긴 자리까지 불이 번져나가며 덮어버리는 경우가 있는데. 단순히 지도에서만 그렇고 지훈이의 좌표는 jihoon 큐 안에 담겨있기 때문에 문제없다.