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

문제

풀이

1. fireMap이라는 새로운 맵을 만들어 최대값으로 초기화 한 후 Fire이 가는 시간(거리)을 채운다.
   (예시 테스트케이스의 fireMap)
   

2. 지훈이 탈출할 수 있는 시간을 구한다.
   a. 탈출구간에 fire이 먼저 왔으면(fireMap의 값이 더 적으면) 탈출 불가능

3. 탈출 못하면 IMPOSSIBLE 출력

코드

for (int i = 0; i < R; i++) {
    String s = fr.nextLine();
    for (int j = 0; j < C; j++) {
        map[i][j] = s.charAt(j);
        fireMap[i][j] = R*C+1;
        if(map[i][j] == 'J'){
            jr = i;
            jc = j;
        }
    }
}

지훈이의 좌표는 따로 채워둔다. fire의 좌표는 여러개가 있을 수 있으므로 나중에 탐색하기로 한다.
fireMap은 입력에서 나올 수 있는 최대값으로 채워놓는다. 나중에 bfs하면서 갱신한다.

for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
        if(map[i][j] == 'F') bfs(i, j, true);
    }
}
bfs(jr, jc, false);
System.out.println(answer);

탐색하면서 Fire을 찾는다. 찾으면 bfs.
fireMap을 다 채우고 나면 지훈이의 좌표로 bfs해 정답 출력한다.

bfs 코드를 살펴보자

public static void bfs(int r, int c, boolean isFire) {
    boolean[][] visit = new boolean[R][C];
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{r, c, 1});
    visit[r][c] = true;
    while (!queue.isEmpty()) {
        int[] poll = queue.poll();
        r = poll[0];
        c = poll[1];
        int dis = poll[2];
        if (isFire) fireMap[r][c] = Math.min(dis, fireMap[r][c]);
        for (int i = 0; i < 4; i++) {
            int nr = r + dir[i][0];
            int nc = c + dir[i][1];
            if (nr < 0 || nc < 0 || nr >= R || nc >= C) {
                if (!isFire) {
                    if (dis < fireMap[r][c]) {
                        answer = String.valueOf(dis);
                        return;
                    }
                }
                continue;
            }
            if (map[nr][nc] != '.') continue;
            if (visit[nr][nc]) continue;
            visit[nr][nc] = true;
            queue.add(new int[]{nr, nc, dis + 1});
        }
    }
}

queue에는 r값, c값, distance값이 들어간다.
평상시와 다르게 boolean 값을 포함하는데 fire이 bfs하는지 지훈이 bfs하는지를 판단하기 위한 boolean 값이다.
fire이면 fireMap을 채워야 하고
지훈이면 정답을 출력해야 하기 때문

• 만약 fire이면
  • 불이 갈 수 있는 위치에 시간(거리)을 기록한다.
    
• 만약 지훈이면(!isFire)
  • 가장자리를 만나면 fireMap의 값과 비교한다.
    • fireMap이 더 적어서 먼저 fireMap이 도착하였으면 탈출할 수 없다.
    • 지훈이의 dis값이 fireMap보다 적어서 빨리 도착했으면 탈출 할 수 있다.

전체코드

package baekjoon._4179;

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 String answer = "IMPOSSIBLE";
    static int R, C;
    static char[][] map;
    static int[][] fireMap;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    public static void input() {
        FastReader fr = new FastReader();
        R = fr.nextInt();
        C = fr.nextInt();
        map = new char[R][C];
        fireMap = new int[R][C];
        int jr = 0;
        int jc = 0;

        for (int i = 0; i < R; i++) {
            String s = fr.nextLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = s.charAt(j);
                fireMap[i][j] = R * C + 1;
                if (map[i][j] == 'J') {
                    jr = i;
                    jc = j;
                }
            }
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'F') bfs(i, j, true);
            }
        }
        bfs(jr, jc, false);
        System.out.println(answer);
    }


    public static void bfs(int r, int c, boolean isFire) {
        boolean[][] visit = new boolean[R][C];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{r, c, 1});
        visit[r][c] = true;
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            r = poll[0];
            c = poll[1];
            int dis = poll[2];
            if (isFire) fireMap[r][c] = Math.min(dis, fireMap[r][c]);
            for (int i = 0; i < 4; i++) {
                int nr = r + dir[i][0];
                int nc = c + dir[i][1];
                if (nr < 0 || nc < 0 || nr >= R || nc >= C) {
                    if (!isFire) {
                        if (dis < fireMap[r][c]) {
                            answer = String.valueOf(dis);
                            return;
                        }
                    }
                    continue;
                }
                if (map[nr][nc] != '.') continue;
                if (visit[nr][nc]) continue;
                visit[nr][nc] = true;
                queue.add(new int[]{nr, nc, dis + 1});
            }
        }
    }

    public static void main(String[] args) {
        input();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

느낀점

98% 쯤에서 오답이 나왔는데 fireMap의 초기화 값을 R*C로 해서였다. 나올 수 있는 최대값보다 +1을 더해야했다.
그리고 처음에는 fireBFS와 jBFS로 bfs의 함수를 두 개로 나눴지만 refactoring하여 하나의 함수로 합쳤다.
BFS 문제는 풀 때마다 재밌는 것 같다.