[백준] 탈출 - Gold 4

[jusung-c]

문제 링크

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

문제 조건

• 빈 칸(.), 물(*), 돌(X)로 이루어진 R x C map에 홍수가 일어난다. (R과 C는 50이하이다)
• 고슴도치(P)는 홍수를 피해 D로 대피해야 한다.
• 고슴도치는 매 분마다 상하좌우로 이동할 수 있으며 물도 매 분마다 상하좌우로 이동한다. (물은 비버의 굴로는 갈 수 없다)
• 고슴도치는 돌과 물을 지나칠 수 없으며 물이 찰 예정인 칸으로도 갈 수 없다.
• 고슴도치가 D로 대피하기 위해 필요한 최소 시간을 구하라, 만약 대피할 수 없다면 "KAKTUS"를 출력한다.

---

아이디어

정답의 최대치

물이 없이 map의 끝에서 끝까지 지그재그로 이동하게 된다면 약 O(N^2)의 시간이 걸릴 것이다.

접근 - 고슴도치의 이동 방법 관찰

다음 턴에 물이 찰 예정인 곳에는 고슴도치가 갈 수 없다. 따라서 이동할 수 있는 빈 칸 중에서 다음 턴에 물이 찰 예정이 아닌 곳을 찾아서 이동하면 되는 것이다.

고슴도치는 인접한 4칸의 후보 이동지 중에 다음 제약 조건을 통과한 곳만 이동할 수 있다.

1. 벽이 아닌 빈칸
2. 물이 찰 예정이 아닌 빈칸

(T+1)의 시간이 되었을 때의 고슴도치와 (W + 1)물의 상태는 다음과 같다.

즉, 고슴도치가 (T + 1)의 시간이 되었을 때와 물이 (W+1)의 시간이 되었을 때의 위치를 비교해서 고슴도치가 갈 수 있는 칸인지 판단하는 작업을 해주면 된다.

접근 - 각 칸이 물에 잠기는 시간 계산

먼저 물이 각 칸에 얼마나 걸리는 지, 즉 각 칸이 언제 물이 잠기는 지 계산해 둬야 고슴도치가 이동할 수 있는 칸인 지 판단할 수 있을 것이다.

물에서 시작하는 BFS를 진행해서 각 위치마다 물이 차는 시간을 계산하자.

그런데 처음 물의 시작점이 하나가 아닌 여러 개이다. 따라서 모든 물마다 BFS를 각자 한 후 각 칸마다 더 적게 걸리는 시간으로 갱신을 하면 될 것이다.

BFS를 한번 진행하는 데엔 O(N^2)의 시간이 걸리고, 물은 최대 N^2개 있을 수 있으므로 최대 시간은 O(N^2*N^2)일 것이다. N은 50이므로 시간 안 풀이가 가능할 것이다.

더 빠르게 할 수 있는 방법은 이전에 배웠던 멀티소스 BFS를 활용하는 것이다. 한 큐에 모든 물의 시작점을 모두 넣고 하는 BFS 방법이다. 어떤 물에서 시작했던 상관없이 모든 물 중에서 가장 빠르게 도착하는 물의 시간을 갱신해주면 될 것이다.

단 한번의 BFS로 끝나기 때문에 O(N^2)의 시간으로 풀이가 가능하다.

접근 - 고슴도치 탈출 시도

이제 각 칸에 물이 잠기는 시간을 전부 아니까 고슴도치의 위치에서 BFS를 통해 물이 잠길 예정인 곳과 벽을 피해서 목적지에 도달할 수 있는 지 확인해주면 된다.

여기서 물이 찰 예정인 곳을 비교할 때 wave 의 값이 -1이 아닌 경우도 걸러내야 한다. 왜냐하면 wave가 -1인 경우는 벽인 경우이거나 목적지인 경우일텐데 벽인 경우는 hog도 -1일테니 상관없지만, 목적지의 경우는 -1이면서 물이 찰 예정이 아닌 곳이기 때문이다.

여기서 내가 놓쳐서 시간을 잡아먹은 부분이 있다.

---

시간 복잡도

1. water BFS 시간: O(V+E) -> O(5050 + 5050*4)
2. �hog BFS 시간: O(V+E) -> O(5050 + 5050*4)

시간 안 풀이가 가능하다.

---

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    ;
    static StringTokenizer st;
    static int R, C;
    static Point S, D;
    static int[][] wave, hog;
    static String[] input;
    static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void init() throws IOException {
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        wave = new int[R][C];
        hog = new int[R][C];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                wave[i][j] = -1;
                hog[i][j] = -1;
            }
        }

        input = new String[R];
        for (int i = 0; i < R; i++) {
            input[i] = br.readLine();
        }
    }

    private static void pro() throws IOException {
        // 물이 잠기는 시간 계산하기
        waveBfs();

        // 고슴도치 시작점 넣기
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (input[i].charAt(j) == 'S') S = new Point(i, j);
                if (input[i].charAt(j) == 'D') D = new Point(i, j);
            }
        }

        // 고슴도치 대피 경로 탐색
        hogBfs(S);

        if (hog[D.x][D.y] == -1) bw.write("KAKTUS");
        else bw.write(hog[D.x][D.y] + " ");
    }

    private static void waveBfs() {
        Queue<Point> que = new LinkedList<>();

        // 모든 물을 시작점으로 넣기
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (input[i].charAt(j) == '*') {
                    que.add(new Point(i, j));
                    wave[i][j] = 0;
                }
            }
        }

        while (!que.isEmpty()) {
            Point p = que.poll();

            // 가능한 모든 경로 BFS 탐색
            for (int d = 0; d < 4; d++) {

                int nx = p.x + dir[d][0];
                int ny = p.y + dir[d][1];

                if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if (wave[nx][ny] != -1) continue;
                if (input[nx].charAt(ny) != '.') continue;

                que.add(new Point(nx, ny));
                wave[nx][ny] = wave[p.x][p.y] + 1;
            }
        }

    }

    private static void hogBfs(Point start) {
        Queue<Point> que = new LinkedList<>();

        que.add(start);
        hog[start.x][start.y] = 0;

        while (!que.isEmpty()) {
            Point p = que.poll();
            for (int d = 0; d < 4; d++) {
                int nx = p.x + dir[d][0];
                int ny = p.y + dir[d][1];

                if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if (hog[nx][ny] != -1) continue;

                // 이동할 수 없는 지역이면 제외
                if (input[nx].charAt(ny) != '.' && input[nx].charAt(ny) != 'D') continue;

                // 물이 잠길 예정이면서 도착지점이 아닌 경우 제외 -> 물에 잠길 예정이어도 도착지점이면 이동 가능
                if (hog[p.x][p.y] + 1>= wave[nx][ny] && wave[nx][ny] != -1) continue;

                que.add(new Point(nx, ny));
                hog[nx][ny] = hog[p.x][p.y] + 1;
            }

        }
    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}