[백준 - G5] 17836. 공주님을 구해라!

문제

용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.

마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈 하고 싶은 용사는 반드시 T시간 내에 공주님이 있는 곳에 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸린다. 공주님이 있는 곳에 정확히 T시간만에 도달한 경우에도 구출할 수 있다. 용사는 상하좌우로 이동할 수 있다.

성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.

우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.

 

문제 풀이

최단 거리를 구하되, 그람이 있다면 벽을 뚫고 갈 수 있다. 이 경우를 고려한 최단 거리를 구하는 문제이다.

 

그람을 보유한 여부에 따라 각 노드가 다른 상태를 가지기 때문에 3차원 방문 배열을 사용해야 한다.
아래와 같이 현재 상태와 다음 상태를 설정해준 이유는 그람을 만나 hasGram = 1을 바로 설정했을 때 문제가 발생한다. 바로 visited[nx][ny][hasGram] = visited[x][y][hasGram] + 1 이 코드에서 visited[nx][ny][1] = visited[x][y][1] + 1 가 된다. 하지만 현재 까지의 방문 횟수는 visited[x][y][0]에 들어있으므로 이전 상태와 다음 상태를 구분해주게 되었다.
그 결과 visited[nx][ny][1] = visited[x][y][0] + 1 로 넣어주어 현재 까지의 방문 횟수 값이 연결될 수 있게 된다.

1. 검을 만났을 경우 상태를 1로 변경한다. 이때 현재 상태(hasGram)는 유지하고 해야하므로 다음 상태(nextGram)를 1로 해야한다.
2. 아직 방문하지 않았을 때
   • 벽일 경우 반드시 검을 보유해야 통과 가능
   • 시간 T를 초과하지 않을 것

 

제출 코드

public class Main {

    static int N, M, T;
    static int[][] map;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");

        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);
        T = Integer.parseInt(split[2]);

        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            split = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(split[j]);
            }
        }

        visited = new int[N][M][2];
        int result = rescue(0, 0);
        if (result == -1 || result > T) {
            System.out.println("Fail");
        } else {
            System.out.println(result);
        }
    }

    static int[][][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static int rescue(int x, int y) {

        Queue<int[]> queue = new ArrayDeque<int[]>();
        queue.offer(new int[]{x, y, 0});
        visited[x][y][0] = 1;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            x = curr[0];
            y = curr[1];
            int hasGram = curr[2];

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
                    continue;
                }

                if (visited[x][y][hasGram] > T) {
                    continue;
                }

                if (nx == N - 1 && ny == M - 1) {
                    visited[nx][ny][hasGram] = visited[x][y][hasGram] + 1;
                    return visited[nx][ny][hasGram] - 1;
                }

                int nextGram = hasGram;
                if (map[nx][ny] == 2) { // 검 획득
                    nextGram = 1;
                }

                if (visited[nx][ny][nextGram] == 0) {
                    // 벽인데, 검이 없을 경우
                    if (map[nx][ny] == 1 && nextGram == 0) {
                        continue;
                    }

                    visited[nx][ny][nextGram] = visited[x][y][hasGram] + 1;
                    queue.offer(new int[]{nx, ny, nextGram});

                }
            }

        }

        return -1;
    }

}

링크

• https://www.acmicpc.net/problem/17836