[BOJ] 4179 : 불! [G4]

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

4179번: 불!

 

 

 

 

[문제]

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

 

[입력]

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

 

[출력]

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

 

[예제 입력 1]

4 4
####
#JF#
#..#
#..#

[예제 출력 1]

3

 

 

[내 풀이]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

/*
	문제 : [G4] 불! - 4179번
	결과 : 통과
	성능 요약 : 메모리 48120KB, 시간 2864ms
	아이디어 :
	    1. 전체 미로를 돌며 지훈이가 위치한 곳과 불이 위치한곳을 큐에 각각 넣어준다.
	    2. 큐에서 하나씩 위치정보를 빼면서 불을 먼저 이동시킨 후, 지훈이가 이동할 수 있으면 이동시키며 escapeTime을 1증가시킨다.
	    3. 더 이상 지훈이가 이동할 수 없을 때 까지 1~2를 반복한다.
	    4. 최종 탈출하는데 걸린 시간을 출력한다.

	    위 방식말고 불길이 가는 시간을 체크하며 모든 bfs를 다 돈 후
	    지훈이의 이동을 체크하면(불길이 가는 시간보다 빨리 움직일 경우 이동가능) 시간복잡도를 훨씬 많이 줄일 수 있을 것 같다...
*/

public class Main_4179_불 {

    static int R, C, escapeTime;
    static boolean isArrive;
    static boolean[][] isJVisited;
    static boolean[][] isFVisited;
    static char[][] miro;
    static int[][] dxdy = {{-1, 0}, {1, 0}, {0, -1}, { 0, 1}};
    static Queue<int[]> qJ = new ArrayDeque<>();
    static Queue<int[]> qF = new ArrayDeque<>();

    static void bfs(int del, int row, int col) {

        // 미로의 가장자리에 접한 공간에서 탈출 가능
        if (del == 1 && (row == 0 || row == R - 1 || col == 0 || col == C - 1)) {
            isArrive = true;
            return;
        }

        for (int i = 0; i < 4; i++) {
            int dx = row + dxdy[i][0];
            int dy = col + dxdy[i][1];

            if (dx >= 0 && dx < R && dy >= 0 && dy < C) {
                // 불길
                if (del == 2 && (miro[dx][dy] == '.' || miro[dx][dy] == 'J')) {
                    miro[dx][dy] = 'F';
                }

                // 지훈이
                else if (del == 1 && miro[dx][dy] == '.') {
                    miro[dx][dy] = 'J';
                }
            }
        }

    }

    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());
        miro = new char[R][C];
        isJVisited = new boolean[R][C];
        isFVisited = new boolean[R][C];

        // 입력받은 문자열을 char형 2차원 배열로 변환
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            miro[i] = st.nextToken().toCharArray();
        }

        // 더이상 지훈이가 이동할 수 없을 때까지 반복
        boolean canMove = true;
        while (canMove) {
            canMove = false;
            // 지훈이와 불 위치 체크
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (!isJVisited[i][j] && miro[i][j] == 'J') {
                        isJVisited[i][j] = true;
                        canMove = true;
                        qJ.offer(new int[]{i, j});
                    } else if (!isFVisited[i][j] && miro[i][j] == 'F') {
                        isFVisited[i][j] = true;
                        qF.offer(new int[]{i, j});
                    }
                }
            }
            // <불보다 지훈이를 먼저 이동시키면 시간초과가 난다!>

            // 불 이동 체크 (F's del == 2)
            while (!qF.isEmpty()) {
                int[] temp = qF.poll();
                bfs(2, temp[0], temp[1]);
            }

            // 지훈이 이동 체크 (J's del == 1)
            escapeTime += 1;
            while (!qJ.isEmpty() && !isArrive) {
                int[] temp = qJ.poll();
                bfs(1, temp[0], temp[1]);
            }

            if (isArrive) break;
        }

        System.out.println(isArrive ? escapeTime : "IMPOSSIBLE");

    }

}

 

<회고>

위 풀이대로 풀게 되면 매 반복마다 불길이 가는 구역과 지훈이가 가는 구역을 계산해야 하기 때문에 로직의 시간복잡도가 높다.

불길이 매 시간마다 가는 구역을 체크 한 후, 지훈이가 그 구역에 도달할 수 있는지 체크하여

반복없이 bfs만 돌아서 답을 구하게 되면 시간복잡도가 훨씬 작게 나올 것 같다.