[BOJ / C++] 17836번 : 공주님을 구해라!

문제

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

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

 

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

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

입력

첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)

두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.

출력

용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.

만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "Fail"을 출력한다.

Solved.ac 레벨

골드 V

풀이

얼핏 보기엔 간단했으나 꽤 많은 시간을 투자한 BFS 문제였다.

처음 시도했을 때는 (0, 0)에서 (n - 1, m - 1)로 이동하는 최단거리 BFS vs 검까지 갔다 검에서 벽 검증 없이 BFS 를 시도했는데 두 값이 계속 같은 값이 나왔다. 디버깅 해보니 둘의 경로가 같았다 --..

 

그래서 방문 확인용 visited 배열을 3차원으로 선언하여 풀이하는 방향으로 노선을 틀었다.

 

visited[x][y][2]로 사용하였는데, [x][y][0]의 경우 검을 획득하지 못한 경우, [x][y][1]은 검을 획득한 경우의 방문 체크다.

검을 획득하지 못한 상태에서는 [x][y][0]에서만 방문 체크를 하였고 벽을 피해 탐색하였으며, 검을 획득한 후부터는 [검 좌표 x][검 좌표 y][1]에서부터 방문 체크를 하며 벽을 무시하고 탐색하였다.

 

검 획득 여부는 BFS를 위한 큐를 pair<<pair<int, int>, pair<bool, int>>> 타입으로 선언하여 사용하였다.

first.fisrt : x 좌표

first.second : y 좌표

second.first : 검 획득 여부

second.second : 이동 거리

 

검을 획득함과 동시에 방문 체크를 1로 돌리는 동시에 큐에도 검을 획득했음을 알렸다.

 

 

예제에 주어진 그림에서 설명해보자면

1. 용사가 있는 (0, 0)에서부터 검이 있는 (0, 5)까지는 [0][0][0] ~ [0][4][0]으로 방문체크를 하며 탐색한다.

2. 다음 좌표에 검 (2)가 있음이 확인되면 방문 체크를 [0][5][1]로 해주며 큐에 false 대신 true를 넣는다.

3. 그 이후로는 벽을 무시하며 최단 경로를 탐색한다.

4. 현재 좌표가 마지막 좌표라면 현재까지의 거리를 출력하고 함수를 종료한다.

4 - 1. 현재 탐색까지 걸린 거리가 입력으로 주어진 t보다 크다면 Fail을 출력하고 함수를 종료한다.

 

코드에 주석으로 달아두겠다.

 

Code

#include<bits/stdc++.h>

using namespace std;

int n, m, t, sy, sx;
int MAP[101][101];
bool visited[101][101][2];
//[][][0] : 그람 안 먹음
//[][][1] : 그람 먹음
pair<int, int> dir[4] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
queue<pair<pair<int, int>, pair<bool, int>>> q;
//first.first : x
//first.second : y
//second.first : sword
//second.second : dist

void BFS() {
    q.push({{0, 0}, {false, 0}});
    //(0, 0) 부터 탐색 시작, 검을 획득하지 않은 상태, 이동 거리 0

    while(!q.empty()) {
        int curX = q.front().first.first;
        int curY = q.front().first.second;
        bool chkSword = q.front().second.first;
        int curDist = q.front().second.second;
        q.pop();

        if(curDist > t) {
        	//현재까지의 이동 거리가 주어진 t보다 크다면 공주를 구할 수 없음.
            cout << "Fail\n";
            return;
        }

        if(curX == n - 1 && curY == m - 1) {
        	//현재 탐색 중인 위치가 공주가 있는 (n, m)이라면 현재까지의 이동 거리를 출력.
            cout << curDist << "\n";
            return;
        }

        for(int i = 0; i < 4; i++) {
            int nxtX = curX + dir[i].first;
            int nxtY = curY + dir[i].second;
            int nxtDist = curDist + 1;

            if(nxtX < 0 || nxtX >= n || nxtY < 0 || nxtY >= m) continue;

            if(chkSword) {
            	//검이 있는 경우는 visited[x][y][1]을 체크
                if(!visited[nxtX][nxtY][1]) {
                	//벽을 뚫을 수 있으므로 벽 검증 없이 탐색
                    visited[nxtX][nxtY][1] = true;
                    q.push({{nxtX, nxtY}, {true, nxtDist}});
                    //검을 획득한 상태이므로 true를 계속해서 큐에 삽입
                }
            } else {
                if(!visited[nxtX][nxtY][0] && MAP[nxtX][nxtY] == 0) {
                	//검을 획득하지 않은 상태, 벽이 없어야 탐색
                    visited[nxtX][nxtY][0] = true;
                    q.push({{nxtX, nxtY}, {false, nxtDist}});
                } else if(!visited[nxtX][nxtY][0] && MAP[nxtX][nxtY] == 2) {
                	//검을 획득하지 않은 상태, 다음 탐색 대상 좌표에 검이 있다면
                    visited[nxtX][nxtY][1] = true;
                    //검이 있는 위치에서부터 [x][y][1]에서 경로 체크
                    q.push({{nxtX, nxtY}, {true, nxtDist}});
                    //검을 획득한 시점에서부터 true를 큐에 삽입
                }
            }
        }
    }

    cout << "Fail\n";

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> t;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> MAP[i][j];
        }
    }

    BFS();

    return 0;

}

 

17836번: 공주님을 구해라!