[BOJ] #13549 숨바꼭질 3

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

13549번: 숨바꼭질 3

---

이전에 작성했던 #1697 숨바꼭질 문제의 연장선상에 있는 문제이다. 당시엔 가중치가 없는 그래프에서 최단 경로를 찾는 형식이었기에, BFS를 이용해서 해결했었지만, 이번엔 가중치가 새로 생겼다. 걸어가는 경우와 순간이동을 하는 경우 두가지 경우의 가중치가 다르기 때문에 BFS가 아닌 다익스트라를 이용하여 문제를 풀어야 한다.

필자가 기존에 다익스트라를 활용하던 방식은 pair형 priority queue를 선언 하고 first에는 인덱스, second에는 가중치의 합을 저장하여 순회하는 방식으로 많이 썼었는데, 이번엔 좀 다르다. visited 배열을 2차원으로 선언하여 [0]에는 방문 여부, [1]에는 가중치의 합을 저장하여 사용하고, priority queue는 그냥 인덱스만 저장한다. 이렇게 하는 이유는, 추후에 순회시에 현재 가중치와 이전 가중치를 서로 비교해야 하는 경우가 생기는데, 이때의 경우를 대비하여 visited 배열을 2차원으로 선언하는 것이다.

	if (n+1>=0 && n+1<MAX && !visited[n+1]) {
            visited[n] = true;
            Q.push(make_pair(n+1, cnt+1));
        }
        if (n-1>=0 && n-1<MAX && !visited[n-1]) {
            visited[n] = true;
            Q.push(make_pair(n-1, cnt+1));
        }
        if (n*2>=0 && n*2<MAX && !visited[n*2]) {
            visited[n*2] = true;
            Q.push(make_pair(n*2, cnt+1));
        }

따라서, 기존 #1697번 문제에서는 if 조건문 분기를 위와 같은 형식으로 했다면...

	if (n*2>=0 && n*2<MAX) {
            if (!visited[n*2][0] || visited[2*n][1] > cnt) {
                visited[2*n][0] = 1;
                visited[2*n][1] = cnt;
                Q.push(2*n);
            }
        }

        if (n+1>=0 && n+1<MAX) {
            if (!visited[n+1][0] || visited[n+1][1] > cnt+1) {
                visited[n+1][0] = 1;
                visited[n+1][1] = cnt+1;
                Q.push(n+1);
            }
        }

        if (n-1>=0 && n-1<MAX) {
            if (!visited[n-1][0] || visited[n-1][1] > cnt+1) {
                visited[n-1][0] = 1;
                visited[n-1][1] = cnt+1;
                Q.push(n-1);
            }
        }

이번 문제에서는 위와 같은 형태로 바꾸어 탐색해주어야 한다. 기존에 사용하던 방문여부를 판별하는 부분과, 현재 가중치와 이전 가중치를 판별하는 부분 모두를 고려하여 최적의 경로를 탐색해야 하기에 OR 연산자를 이용하여 작성했다.

struct cmp{
    bool operator()(int n1,int n2){
        if(visited[n1][1]>visited[n2][1]){
            return true;
        }//시간에 따라 우선순위 부여
        else{
            return false;
        }
    }
};

priority_queue<int,vector<int>,cmp> Q;

또한, priority queue를 사용하기에 정렬 기준 또한 새로 만들어 부여해주어야 한다. 기존엔 그냥 음수로 바꿔서 저장하는 방식으로 사용했었지만, 이번 문제에서는 그렇게 저장하고 사용하다간 너무 헷갈릴거 같아서 그냥 따로 operator함수를 부여해주었다. 그로 인해 priority queue 선언 방식도 위와 같이 선언해주어야 한다.

 

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

#define MAX 100001

using namespace std;

int N,K;
int visited[MAX][2];
//[0]엔 방문 여부, [1]엔 시간 저장

struct cmp{
    bool operator()(int n1,int n2){
        if(visited[n1][1]>visited[n2][1]){
            return true;
        }//시간에 따라 우선순위 부여
        else{
            return false;
        }
    }
};

priority_queue<int,vector<int>,cmp> Q;

int F(int a, int c) {
    visited[a][0] = 1;
    visited[a][1] = 0;
    Q.push(a);

    while (!Q.empty()) {
        int n = Q.top();
        int cnt = visited[n][1];
        Q.pop();

        if (n == K) return cnt;

        if (n*2>=0 && n*2<MAX) {
            if (!visited[n*2][0] || visited[2*n][1] > cnt) {
                visited[2*n][0] = 1;
                visited[2*n][1] = cnt;
                Q.push(2*n);
            }
        }

        if (n+1>=0 && n+1<MAX) {
            if (!visited[n+1][0] || visited[n+1][1] > cnt+1) {
                visited[n+1][0] = 1;
                visited[n+1][1] = cnt+1;
                Q.push(n+1);
            }
        }

        if (n-1>=0 && n-1<MAX) {
            if (!visited[n-1][0] || visited[n-1][1] > cnt+1) {
                visited[n-1][0] = 1;
                visited[n-1][1] = cnt+1;
                Q.push(n-1);
            }
        }
    }
    return 0;
}

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

    cin >> N >> K;

    cout << F(N,0) << '\n';

    return 0;
}

전처리기를 잘못 입력해서 OutOfBounds 런타임 에러가 떴다...