[알고리즘 풀이 분석] BOJ 17386 공주님을 구해라!

오늘 풀어본 문제는 BOJ 17386 공주님을 구해라! 이다. 기본적인 그래프 탐색 문제에 하나의 변수가 더 추가된 형태이고 골드 5 단계의 문제이다. 요즘 좀 느슨해져서 그런가 왜 골드 5도 좀 버겁냐,,?ㅜ

BOJ 17386 공주님을 구해라!

용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (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"을 출력한다.

나의 풀이

이전에도 풀어봤던 그래프 탐색 문제 유형이었다.
기본적인 탐색 방법을 사용하면서 약간의 트릭을 함께 해결하는 형태

다뤄야 하는 정보는 탐색 위치 + 소요 시간 + 그람 소유 유무 세가지 였다!

queue 를 사용해 탐색을 진행하면서 현재 그람을 소유하고 있는지 아닌지를 함께 큐에 넣어주고 소요 시간은 3차원 배열을 이용해 dp 형식으로 적어주었다.

현재 위치를 기준으로 도달 가능한 인접 칸을 탐색하고 1 - 해당 칸이 지도 범위를 벗어날 경우, 2 - 벽이지만 그람을 소유하지 않았을 경우, 3 - 현재까지의 소요시간보다 더 작은 시간이 적혀있을 경우를 제외하고 큐에 넣어준다.

난 처음에 그람이 있는 칸을 탐색할 경우 그람 소유 여부를 바로 바꿔주지 않고 그 다음부터 바꿔주려 했는데 바로 바꾸어야 그람을 소유한채로 벽을 부수면서 진행해 나갈 수 있다는 점을 놓쳐 한번에 통과하지 못했다.

문제를 통과한 이후 다른 풀이를 찾아보다가 3의 경우 굳이 최소 시간인지를 확인할 필요 없이 방문 이력이 있다면 이미 최소 시간이기 때문에 방문 여부만 확인하면 된다는 걸 알게 되었는데,, BFS 문제를 많이 풀었기 때문에 직관적으로 와닿기는 하지만 논리적으로 좀 덜 와닿는 것 같다..

하지만 방문 처리만 한 코드로 수정해서 통과도 되긴 했다,, 왜일까,,

또 훨씬 간단한 아이디어를 얻었는데,
그람을 소유한 뒤엔 무조건 도달 가능하기 때문에 그람이 있는 칸 부터 공주님이 있는 칸 까지의 절대적인 거리만 구해서 더해주면 된다는 것이다.

검을 소유하지 않고 도달 가능한 시간을 구하고 검을 구했다면 공주님이 있는 위치까지의 거리만을 구해서 최소 시간인지만 확인하면 되는 것이다..!

이렇게 푼다면 3차원 배열을 사용할 필요도 없고 일반적인 BFS 를 진행하면서 검을 찾기만 하면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>

// boj 17386 공주님을 구해라!, BFS, 골드 5
using namespace std;

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

int MINTIME = -1;
vector<vector<int>> castle;

bool savePrincess(int N, int M, int T){
    bool result = false;
    vector<vector<vector<int>>> dp(N+1, vector<vector<int>>(M+1, vector<int>(2, 10001)));

    queue<pair<pair<int, int>, int>> point;
    point.push({{1,1}, 0});
    dp[1][1][0] = 0;

    while (!point.empty()){
        int row = point.front().first.first;
        int col = point.front().first.second;
        int flag = point.front().second;
        point.pop();

        if (row==N && col==M){
            result = true;
            continue;
        }

        if (dp[row][col][flag] == T) continue;

        for (int i = 0; i < 4; ++i) {
            int nr = row + dy[i];
            int nc = col + dx[i];

            if (nr<1 || nr>N || nc<1 || nc>M ) continue;
            if (castle[nr][nc] == 1 && flag == 0) continue;
            if (dp[nr][nc][flag] != 10001) continue;


            if(castle[nr][nc] == 2){
                dp[nr][nc][1] = dp[row][col][flag] + 1;
                point.push({{nr, nc}, 1});
            }else{
                dp[nr][nc][flag] = dp[row][col][flag] + 1;
                point.push({{nr, nc}, flag});
            }
        }
    }

    if(result){
        MINTIME = min(dp[N][M][0], dp[N][M][1]);
    }

    return result;
}


int main() {
    int N, M, T;
    cin>>N>>M>>T;

    castle.assign(N+1,vector<int>(M+1));
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            cin>>castle[i][j];
        }
    }

    if (savePrincess(N, M, T)){
        cout<<MINTIME;
    }else{
        cout<<"Fail";
    }

    return 0;
}