불!

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

문제설명

풀이방식

1. BFS를 2번 수행해 문제를 풀려한다.
   why? → 불이 번지기 전에 지훈이가 탈출해야하는데, 불은 매분 한칸씩 번지기 때문에 불이 번지는 시간을 먼저 체크한 뒤, 지훈이가 이동하며 지훈이의 이동시간과 불이 번진 시간을 비교할 생각이다.

2. 동일한 방식으로 BFS를 수행하되, 다음 노드를 탐색하는 조건에서 약간의 차이가 있다.

• 불이 번지는 경우 빈 땅일 경우만 탐색하면 되기 때문에 문제 없다.
• 지훈이의 경우 다음 땅에 도달할때 불보다 빨리 도착해야하기 때문에
  map[nx][ny] > 지훈이가 다음땅에 도달할 시간 이어야한다.
  위의 조건 때문에 visited 배열을 따로 두어 방문한 곳을 다시 방문하지 않도록 해야한다.

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int col = Integer.parseInt(st.nextToken());
        int row = Integer.parseInt(st.nextToken());
        int[][] map = new int[row][col];
        boolean[][] visited = new boolean[row][col]; // 지훈용
        ArrayDeque<int[]> q = new ArrayDeque<>(); // x, y, fs
        int sx = 0;
        int sy = 0;

        for (int i = 0; i < row; i++) {
            String str = bf.readLine();
            for (int j = 0; j < col; j++) {
                char c = str.charAt(j);
                if (c == 'J') {
                    sx = i;
                    sy = j;
                    map[i][j] = -1; // 시작점
                } else if (c == 'F') {
                    map[i][j] = -2; // 불
                    q.offer(new int[]{i, j, 0});
                } else if (c == '#') {
                    map[i][j] = -3; // 벽
                } else {
                    map[i][j] = 0; // 번질 수 있는 곳
                }
            }
        }

        int[] dr = new int[]{-1, 1, 0, 0};
        int[] dc = new int[]{0, 0, -1, 1};

        // 불 점화
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];
            int cf = cur[2];

            for (int i = 0; i < 4; i++) {
                int nx = cx + dr[i];
                int ny = cy + dc[i];
                int nf = cf + 1;

                if (nx > -1 && nx < row &&
                        ny > -1 && ny < col &&
                        map[nx][ny] == 0) {
                    q.offer(new int[]{nx, ny, nf});
                    map[nx][ny] = nf;
                }
            }
        }

        q.offer(new int[]{sx, sy, 0});
        int min = Integer.MAX_VALUE;
        visited[sx][sy] = true;
        boolean escape = false;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];
            int cf = cur[2];

            // 가장 먼저 접하는게 가장 빠른 경우 아닐까
            if (cx == row - 1 || cx == 0 || cy == col - 1 || cy == 0) {
                min = cf;
                escape = true;
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nx = cx + dr[i];
                int ny = cy + dc[i];
                int nf = cf + 1;

                if (nx > -1 && nx < row && ny > -1 && ny < col &&
                    map[nx][ny] != -3 && // 벽이 아니고
                    map[nx][ny] != -2 && // 불도 아니고
                    (map[nx][ny] > nf || map[nx][ny] == 0) &&
                    !visited[nx][ny]){// 불보다 빨리 도착하거나 불이 도달하지 않았거나
                    q.offer(new int[]{nx, ny, nf});
                    visited[nx][ny] = true;
                }
            }
        }

        if (escape) System.out.println(min + 1);
        else System.out.println("IMPOSSIBLE");
    }
}

---

DFS 정복주를 지나고 있는데 어느정도 난이도가 있는 문제도 풀어낼 수 있다는게 뿌듯하다! 화이링링~