BOJ - 13549 숨바꼭질3

13549번 숨바꼭질3

시작점과 끝점이 주어지고 시작점에서 끝점 까지 이동할 때의 최단 시간을 구하는 문제이다. 이동은 +1, -1, x2로 할 수 있으며, +-로 이동할 때 1초가 걸리며 x2로 이동할 때는 0초가 걸린다.

시작점으로부터 세 가지의 이동 방법에 따라 위치가 바뀌고 끝 점에 도달했을 때의 최단 시간을 구하는 문제로 시작점 부터 끝점까지의 이동은 bfs를 통해 해결할 수 있다.

그리고 이동 방법에 따라 걸리는 시간이 다른데 최소 시간을 구하는 것이므로 우선순위 큐(priority queue) 혹은 덱(deque)를 이용할 수 있다.

priority queue 사용

+-로의 이동은 1초가 걸리므로 우선순위를 낮게, x2로의 이동은 0초가 걸리므로 우선순위를 높게 줘서 우선순위 큐를 이용할 수 있다.

구현은 우선순위 큐를 pair형식으로 구현하여 first인자로 시간을, second인자로 위치를 부여해 주었다.

코드

#include <iostream>
#include <queue>

using namespace std;

int visited[100001];

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

    int s,e;
    cin >> s >> e;

    priority_queue<pair<int,int>> q;
    q.push(make_pair(0,s));

    int x,t;

    while(!q.empty())
    {
        t = -1 * q.top().first;
        x = q.top().second;
        q.pop();

        if(x == e)
            break;

        if(visited[x] == 1)
            continue;
        else
        {
            visited[x] = 1;

            if(x + 1 <= 100000)
                q.push(make_pair(-(t+1),x+1));

            if(x - 1 >= 0)
                q.push(make_pair(-(t+1),x-1));

            if(x*2 <= 100000)
                q.push(make_pair(-t,x*2));
        }
    }

    cout << t;

    return 0;
}

deque 사용

덱의 경우 앞뒤로 인자를 삽입, 추출 할 수 있다. 따라서 우선순위가 높은 x2의 이동은 앞으로 넣어주고, 우선순위가 낮은 +-의 이동은 뒤로 넣어줘서 앞에서 부터 pop하며 사용하면 된다.

마찬가지로 pair형식으로 위치와 시간을 부여해 주었다.

코드

#include <iostream>
#include <deque>

using namespace std;

int visited[100001];

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

    int s,e;
    cin >> s >> e;

    deque<pair<int,int>> dq;
    dq.push_back(make_pair(0,s));

    int x,t;

    while(!dq.empty())
    {
        t = -1 * dq.front().first;
        x = dq.front().second;
        dq.pop_front();

        if(x == e)
            break;

        if(visited[x] == 1)
            continue;
        else
        {
            visited[x] = 1;

            if(x + 1 <= 100000)
                dq.push_back(make_pair(-(t+1),x+1));

            if(x - 1 >= 0)
                dq.push_back(make_pair(-(t+1),x-1));

            if(x*2 <= 100000)
                dq.push_front(make_pair(-t,x*2));
        }
    }

    cout << t;

    return 0;
}

아래의 결과가 우선순위 큐를 활용한 코드이고 위의 결과가 덱을 활용한 코드이다. 두 코드만 보면 크게 다른점은 없는데 메모리나 시간이 크게 차이가 난다.

이는 우선순위 큐의 경우 삽입 및 삭제 시에 O(logn)의 시간이 걸리는 반면 덱의 경우 삽입 삭제 시 O(1)만 걸리기 때문이다.

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