[Gold IV][JAVA]백준 4179번:불!

문제 바로가기> [Gold IV]백준 4197번:불!

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

1.이동

• 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
• 불은 각 지점에서 네 방향으로 확산된다. (상하좌우)
• 지훈이의 이동이 불의 전파에 영향을 받지만, 불의 전파는 지훈이의 이동에 영향을 받지 않음
  => 불 전파를 먼저 시킨다.

코드

• 지훈이의 위치와 불의 위치를 Queue에 저장
• 불이 먼저 퍼지는데, 범위를 벗어나거나 #(벽), 이미 방문한 경우는 pass
• 불이 퍼지고 지훈이가 이동한다. 범위를 벗어나면 지훈이는 탈출을 하게 되고, #(벽)이거나 F(불)이거나 이미 방문한 곳이라면 pass

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main { 
    static int R, C, res;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static char[][] map;
    static Queue<Pair> fire = new LinkedList<>();
    static Queue<Pair> jh = new LinkedList<>();
    static class Pair {
        int x, y, d;

        public Pair(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
    public static void main(String argsp[]) 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()); // 열
        map = new char[R][C];

        for (int i = 0; i < R; i++) {
            String info = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = info.charAt(j);

                if (map[i][j] == 'F')
                    fire.add(new Pair(i, j, 0));
                else if (map[i][j] == 'J')
                    jh.add(new Pair(i, j, 0));

            }
        }
        if (bfs()) System.out.println(res);
        else System.out.println("IMPOSSIBLE");
    }

    public static boolean bfs() {
        while (!jh.isEmpty()) {
            // 불 전파 먼저
            int size = fire.size();

            for (int i = 0; i < size; i++) {
                Pair now = fire.poll();
                for (int d = 0; d < 4; d++) {
                    int dr = now.x + dx[d];
                    int dc = now.y + dy[d];

                    if (dr < 0 || dc < 0 || dr >= R || dc >= C) continue;
                    if (map[dr][dc] == '#' || map[dr][dc] == 'F') continue;

                    map[dr][dc] = 'F';
                    fire.add(new Pair(dr, dc, now.d + 1));
                }
            }

            // 지훈 이동
            size = jh.size();

            for (int i = 0; i < size; i++) {
                Pair now = jh.poll();
                for (int d = 0; d < 4; d++) {
                    int dr = now.x + dx[d];
                    int dc = now.y + dy[d];

                    if (dr < 0 || dc < 0 || dr >= R || dc >= C) {
                        res = now.d + 1;
                        return true;
                    }
                    if (map[dr][dc] == '#' || map[dr][dc] == 'F' || map[dr][dc] == 'J') continue;

                    map[dr][dc] = 'J';
                    jh.add(new Pair(dr, dc, now.d + 1));
                }
            }
        }
        return false;
    }
}