Q. 4179 자바 : 불!

Q. 4179 자바 : 불!

 

문제 : boj.kr/4179

골드 4 난이도의 문제이고, 탈출 문제와 유사하다

 

탈출해야 하는 지훈이와 불이 주어지고 불은 점점 확산된다.

이 때 얼마나 빨리 지훈이가 탈출할 수 있는지 계산하는 문제이다.

 

주의해야 할 점은 불과 지훈이가 같이 있는 경우 탈출할 수 없다.

그래서 BFS 탐색을 사용하기 전에 불을 먼저 queue에 넣어주고 지훈이의 위치를 마지막에 넣었다.

또한 탈출하는 경우는 미로의 가장자리에 있는 경우이고, 탈출 시 이동 횟수가 하나 늘어난다. 

 

아래와 같은 방식으로 풀었다.

1. 입력값은 visit 배열을 이용해서 받았고, 벽(#), 지훈이(J), 화염(F) 모두 방문 체크를 했다.

2. 입력을 받을 때 지훈이와 불의 위치를 모두 저장한 뒤 BFS 탐색 전 큐에 불의 위치를 먼저 넣고

지훈이의 위치를 마지막에 넣었다(불이 있는 경로로 지훈이가 이동할 수 없으므로)

한다는 내용 때문에 그래프를 입력 받은 뒤 정렬이 한번 필요하다

3. 이후 visit 배열을 이용해 불이 있는 위치와 기존에 방문한 위치를 탐색하지 않게 구현했고,

BFS를 이용해 불과 지훈이의 이동을 구현해 답을 구했다.

+ 지훈이가 시작 위치에서 탈출할 수 있는 경우를 BFS 탐색 전에 먼저 체크했다.

 

시간 복잡도를 계산하면, .

R, C의 최대값이 1000이지만, 불과 지훈이 모두 기존에 방문했던 곳은 탐색하지 않으므로

1. 모든 정점 BFS 탐색 - O(R * C)

모든 정점을 탐색하는 경우가 최악의 경우이므로 시간 초과는 걱정하지 않아도 된다.

 

자료형은 bool형 2차원 배열을 이용해 그래프와 방문 여부를 구현했고, 

이후 BFS 탐색에 필요한 좌표와 이동 횟수는 int형 배열로 구현했다. 

 

풀이는 아래와 같다.

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int r, c;
    static char[][] Graph;
    static boolean[][] visit;
    static int[] dy = new int[] {0, 1, 0, -1};
    static int[] dx = new int[] {1, 0, -1, 0};
    static ArrayList<int[]> fireArr;
    static int[] start;

    static void input(){

        r = scan.nextInt();
        c =  scan.nextInt();
        fireArr = new ArrayList<>();

        visit = new boolean[r][c];
        for (int i = 0; i < r; i++) {
            char[] inputArr = scan.nextLine().toCharArray();;
            for (int j = 0; j < c; j++) {
                if (inputArr[j] == '.') continue;
                visit[i][j] = true;
                if (inputArr[j] == 'F') {
                    fireArr.add(new int[] {i, j, -1});
                } else if (inputArr[j] == 'J') {
                    start = new int[] {i, j, 0};
                }
//                else if (inputArr[j] == '#') {
//                    visit[i][j] = true;
//                }
            }
        }
    }

    static void pro() {

        int res = bfs();
        if (res == -1) System.out.println("IMPOSSIBLE");
        else System.out.println(res);
    }

    static int bfs() {

        if (start[0] == 0 || start[1] == 0 || start[0] == (r - 1) || start[1] == (c - 1))
            return 1;
        Queue<int[]> que = new LinkedList<>();

        que.addAll(fireArr);
        que.add(start);

        while (!que.isEmpty()) {

            int[] cur = que.poll();
            // cur[0] = y
            // cur[1] = x
            // cur[2] = J : moveCnt, fire : -1

            for (int i = 0; i < 4; i++) {
                int ny = cur[0] + dy[i];
                int nx = cur[1] + dx[i];

                if (ny == -1 || nx == -1 || ny == r || nx == c) continue;
                if (visit[ny][nx]) continue;
                visit[ny][nx] = true;

                if (cur[2] != -1) {
                    if (ny == 0 || nx == 0 || ny == (r - 1) || nx == (c - 1)) {
                        return cur[2] + 2; // move + 1, escape + 1
                    }
                    que.add(new int[] {ny, nx, cur[2] + 1});
                } else {

                    que.add(new int[] {ny, nx, -1});
                }
            }
        }
        return -1;
    }

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


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

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

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

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

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

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

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