[BOJ알고리즘, C++]#13549_숨바꼭질3, 우선순위 큐

 

#1. 문제

 

 

---

 

#2. 풀이

 

1. 우선순위 큐

[Basic C++] #69_priority_queue

 

[정의] : C++의 STL에서 제공하는 priority_queue 컨테이너는 각 항목에 우선순위를 부여해 힙 자료구조에 저장하는 자료구조입니다.

[특징] : priority_queue는 세 번째 인자로 전달받은 비교 함수를 통해 최소 힙 혹은 최대 힙을 구성합니다. 그리고, 각 항목은 우선순위를 부여받아, 우선순위가 높은 항목이 먼저 처리되는 컨테이너입니다.

[성능] : prioriy_queue의 삽입/삭제 연산은 최악의 경우 시간 복잡도 O(log n)을 갖습니다.

 

2. 순간 이동해보고, 안되면 걷자

 

1. pair< 이동 거리, 현재 위치 > 형식의 항목을 처리하는 우선순위 큐를 선언합니다. 그리고, 우선순위 큐의 정렬 기준은 이동 거리를 기준으로 최소 힙으로 설정합니다. 따라서, 총 이동 거리가 더 짧은 항목이 우선적으로 처리될 수 있도록 합니다.
2. 가장 먼저, 순간 이동을 고려합니다. 다음 위치는 (현재 위치*2)가 되며, 이동 거리에 변화가 없습니다.
3. 다음으로, 걷기를 고려합니다. 다음 위치는 (현재 위치 + 1) 혹은, (현재 위치 - 1)이 되며, 이동 거리에 +1을 해줍니다.
4. 최종적으로, 우선순위 큐에서 가장 우선순위가 높은 항목은 이동 거리의 합이 가장 적은 항목이 되며, 현재 위치가 주어진 도착 위치가 될 때, 총 이동 거리의 합을 출력하고 종료합니다.

 

---

 

#3. 코드

// 실패 코드, 이유는 몰루?

#include <iostream>
#include <vector>
#include <string>
#include <deque>
using namespace std;

#define MAX 100001

int N, K;

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

    cin >> N >> K;

    // #1. 최소 비용 목록
    vector<int> dist(MAX, 0);
    // deque 활용
    deque<int> dq;

    dq.push_front(N);
    dist[N] = 1;

    while (!dq.empty())
    {
        int cur_vertex = dq.front();
        dq.pop_front();

        if (cur_vertex == K)
        {
            cout << dist[cur_vertex] - 1;
            break;
        }

        // #1. 순간 이동일 경우, 방문 여부 체크, 거리 비용 변화 없음, deque의 앞으로 2*cur_vertex 삽입
        if (cur_vertex * 2 < MAX && dist[cur_vertex * 2] == 0)
        {
            dist[cur_vertex * 2] = dist[cur_vertex];
            dq.push_front(cur_vertex * 2);
        }
        // #2. 달리기 +1 일 경우, 방문 여부 체크, 거리 비용 변화 +1, deque의 뒤로 1+cur_vertex 삽입
        if (cur_vertex + 1 < MAX && dist[cur_vertex + 1] == 0)
        {
            dist[cur_vertex + 1] = dist[cur_vertex] + 1;
            dq.push_back(cur_vertex + 1);
        }
        // #3. 달리기 -1 일 경우, 방문 여부 체크, 거리 비용 변화 +1, deque의 뒤로 cur_vertex-1 삽입
        if (cur_vertex - 1 >= 0 && dist[cur_vertex - 1] == 0)
        {
            dist[cur_vertex - 1] = dist[cur_vertex] + 1;
            dq.push_back(cur_vertex - 1);
        }
    }

    return 0;
}

//****************************************************************************************************

// 정답 코드, 우선순위 큐 활용

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

#define MAX 100001

int N, K;

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

    cin >> N >> K;

    // 우선순위 큐 선언
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<bool> visited(MAX, false);

    pq.push({0, N});
    visited[N] = true;

    while (!pq.empty())
    {
        int cur = pq.top().second;
        int dist = pq.top().first;

        pq.pop();

        if (cur == K)
        {
            cout << dist;
            break;
        }

        if (cur * 2 < MAX && !visited[cur * 2])
        {
            visited[cur * 2] = true;
            pq.push({dist, cur * 2});
        }
        if (cur + 1 < MAX && !visited[cur + 1])
        {
            visited[cur + 1] = true;
            pq.push({dist + 1, cur + 1});
        }
        if (cur - 1 >= 0 && !visited[cur - 1])
        {
            visited[cur - 1] = true;
            pq.push({dist + 1, cur - 1});
        }
    }

    return 0;
}

 

---