백준 17836번 <공주님을 구해라!>

백준 알고리즘 17836번

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

17836번: 공주님을 구해라!

---

17836번

N x M 크기의 성이 있다. 성의 입구는 (1, 1)이며, 공주는 (N, M)에 갇혀있다. 이 성에는 여러 개의 마법 벽이 존재한다.

용사는 상하좌우로 이동하며 마왕이 가둬놓은 공주를 구하러 가는데, 공주가 저주에 걸려 T시간 안에 구해야 한다. 또한 용사는 그람(전설의 검)을 획득했을 때만 마법 벽을 부술 수 있다. (마법 벽을 부수는데 제한은 없다.)

성에는 그람 1개만 숨겨져 있고 그람을 획득하자마자 사용할 수 있다.

 

T시간 이내에 구출할 수 없으면 Fail을 출력하고 구출할 수 있다면 공주를 구하는데 걸리는 최소 시간을 출력하면 된다.

---

문제 해결

BFS를 사용해 문제를 해결했다.

 

문제를 읽어보면 그람 없이 공주를 구하거나, 그람 있이 공주를 구하거나, 공주를 못 구하는 경우 3가지가 있을 수 있다.

따라서 그람 없이 공주를 구하는데 걸리는 시간, 그람 있이 공주를 구하는데 걸리는 시간을 구하고, 이 2개의 시간 중 더 작은 시간을 가지고 공주를 구할 수 있는지 확인하면 된다.

 

work2goal(int[] goal) 함수를 만들어서 성의 입구에서 goal까지 가는데 걸리는 시간을 구했다.

work2goal(int[] goal)

• BFS 알고리즘을 이용해서 성의 입구인 (0, 0)부터 goal까지 걸리는 시간을 구했다.
• 먼저 성의 입구를 큐에 넣고, 방문 체크를 진행한다.
• 큐에서 위치를 꺼내서 다음의 과정을 진행한다.
  • 큐에서 꺼낸 위치에서 상하좌우로 움직인다. 이때, 성을 벗어나거나 이미 방문한 위치거나, 벽이라서 못 가는 경우라면 가지 않는다.
  • 만약 새로운 위치가 goal이라면 그때의 시간에 1을 더해서 반환한다.
• 큐에 아무것도 없다면 goal에 도착하지 못했다는 의미이기 때문에 큰 값(Integer.MAX_VALUE)를 반환한다.

그람 없이 공주를 구하는 시간은 work2goal( {N-1, M-1} ) 를 통해 구할 수 있다.

그람 있이 공주를 구하는 시간은 그람이 있는 곳까지 가는 시간과 그람이 있는 곳에서 (N-1, M-1)까지의 최단 시간을 더하면 된다. 따라서 work2goal( 그람이 있는 곳) + (N-1 - 그람의 위치 세로) (M-1 - 그람의 위치 가로) 로 구할 수 있다.

 

두 개의 값 중 공주를 못 구하는 경우를 거르고 최소 시간을 구하고 T 시간 이내인지 판단해 출력하면 된다.

---

코드

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

public class BOJ_17836 {
    static int N, M;
    static int[] di = {1, -1, 0, 0};
    static int[] dj = {0, 0, 1, -1};
    static int[][] board;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inArr = br.readLine().split(" ");
        N = Integer.parseInt(inArr[0]);
        M = Integer.parseInt(inArr[1]);
        int T = Integer.parseInt(inArr[2]);
        int[] knife = new int[2];
        board = new int[N][M];
        for (int i = 0; i < N; i++) {
            inArr = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(inArr[j]);
                if (board[i][j] == 2) knife = new int[]{i, j};
            }
        }
        // end input

        // 용사가 바로 공주가 있는 곳까지 가는 시간 (0, 0) -> (N-1, M-1)
        int direct = work2goal(new int[]{N - 1, M - 1});

        // 용사가 검이 있는 곳까지 가고 (0, 0) -> knife, 검을 들고 공주가 있는 곳까지 가는 시간 knife -> (N-1, M-1)
        int weapon = breakWall(work2goal(knife), knife);

        int answer = Math.min(direct, weapon);
        System.out.println(answer > T ? "Fail" : answer);
    }

    static int breakWall(int curr, int[] knife) {
        if (curr == Integer.MAX_VALUE) return Integer.MAX_VALUE;
        return curr + (N - 1 - knife[0]) + (M - 1 - knife[1]);
    }

    static int work2goal(int[] goal) {
        boolean[][] visit = new boolean[N][M];
        Queue<int[]> Q = new ArrayDeque<>();
        visit[0][0] = true;
        Q.add(new int[]{0, 0});
        int time = 0;
        while (!Q.isEmpty()) {
            int size = Q.size();
            for (int s = 0; s < size; s++) {
                int[] pnt = Q.poll();
                for (int k = 0; k < 4; k++) {
                    int ni = di[k] + pnt[0];
                    int nj = dj[k] + pnt[1];
                    if (ni < 0 || nj < 0 || ni >= N || nj >= M) continue;
                    if (visit[ni][nj] || board[ni][nj] == 1) continue;
                    if (ni == goal[0] && nj == goal[1]) return time + 1;
                    visit[ni][nj] = true;
                    Q.add(new int[]{ni, nj});
                }
            }
            time++;
        }
        return Integer.MAX_VALUE;
    }
}

---

결과

---