[백준 03055] 탈출 [Java]

문제

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

 

---

풀이

S에 위치한 고슴도치가 비버의 굴 D로 이동하는데 필요한 최소 시간을 구하는 문제다.

동시에, 물 또한 인접한 영역으로 퍼져나간다.

• 물이 찰 예정인 영역은 고슴도치가 갈 수 없다. → 고슴도치보다 물 먼저 퍼져야 한다.
• 물은 비버의 굴로 퍼질 수 없다.

우선, 상수들을 정의해주자.

    final static char EMPTY = '.', WATER = '*', START = 'S', END = 'D';
    static int[][] D = {
            {1, 0}, {-1, 0},
            {0, 1}, {0, -1}
    };
    static int R, C;
    static char[][] board;
    static boolean[][] visited;

돌의 위치는 중요하지 않다.

구현 방식에 따라 다르지만, 고슴도치가 물보다 먼저 움직인 후 물이 덮는다 하더라도 큐에는 이미 물로 가득 찬 지역에 위치한 고슴도치의 위치가 있을 것이다.

따라서 물을 먼저 채운 후, 고슴도치가 이동하는 방식으로 구현했다.

물을 채우는 코드는 다음과 같다.

고슴도치보다 먼저 탐색하므로 EMPTY만 채우면 된다.

동시에, 물의 위치를 저장하는 큐에 다시 삽입하기 때문에 순회할 요소의 개수를 미리 구해주었다.

        while (!hedgehogQueue.isEmpty()) {
            int waterSize = waterQueue.size();
            while (waterSize-- > 0) {
                int[] cur = waterQueue.poll();
                final int x = cur[0], y = cur[1];
                for (int[] d : D) {
                    final int nx = x + d[0], ny = y + d[1];
                    if (isValid(nx, ny) && board[nx][ny] == EMPTY) {
                        board[nx][ny] = WATER;
                        waterQueue.add(new int[]{nx, ny});
                    }
                }
            }

다음으로 고슴도치의 이동을 처리하는 코드다.

고슴도치는 END 또는 EMPTY만 갈 수 있다.

만약 END라면 탐색 종료 후 측정 한 시간을 반환하고, EMPTY이면서 방문하지 않은 영역이라면 방문하면 된다.

            int hedgehogSize = hedgehogQueue.size();
            while (hedgehogSize-- > 0) {
                int[] cur = hedgehogQueue.poll();
                final int x = cur[0], y = cur[1];
                for (int[] d : D) {
                    final int nx = x + d[0], ny = y + d[1];
                    if (isValid(nx, ny)) {
                        if (board[nx][ny] == END) {
                            return time + 1;
                        }
                        if (board[nx][ny] == EMPTY && !visited[nx][ny]) {
                            visited[nx][ny] = true;
                            board[nx][ny] = START;
                            hedgehogQueue.add(new int[]{nx, ny});
                        }
                    }
                }
            }
            ++time;
        }
        return -1;

hedgehogQueue 가 만약 비어있다면 waterQueue 에 관계없이 고슴도치가 비버의 굴에 도착하지 못한채로 끝난 경우이다. -1을 반환해 “KAKTUS”를 출력하면 된다.

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/03055.java