[백준] 13549.cpp : 숨바꼭질 3

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

---

• 2배의 위치로 이동하는 경우는 0초 증가가 되기 때문에, 한 틱 별로 큐에 있는 모든 위치를 검사하는 방법은 어렵기 때문에, 큐에 값을 저장할 때, 위치 별로 해당 시간을 같이 저장한다.
• visited 배열로 방문 검사를 해줄 때, 방문 여부만 검사하면 최단 거리가 갱신되지 않을 수 있다.
• 거리에 대한 정보를 저장하게 하고, 최단 거리 갱신이 가능할 때만 큐에 푸시하면서 업데이트 해준다.
• 이 경우, 최단 거리에 대한 판단을 하지 못하기 때문에 큐에 있는 모든 위치를 검사해야 한다.

---

#include <iostream>
#include <queue>

using namespace std;

int n, k;
int visited[100001];
priority_queue<pair<int,int>> q;

void check(int n, int next)
{
    if((0 <= n && n <= 100000) && visited[n] > next)    // 인덱스 검사, 최단 거리 여부 검사 후
    {
        visited[n] = next;                      // 최단 거리 갱신하고
        q.push(pair<int,int>(-next, n));        // 큐에 해당 노드 푸시
    }
}

int main(void)
{
    for(int i = 0 ; i <= 100000 ; i++)          // 초깃값은 이상값으로 설정
        visited[i] = 100001;

    cin >> n >> k;
    q.push(pair<int,int>(0, n));
    visited[n] = 0;                             // 시작 노드 설정
    
    while(q.size())
    {
        int pos = q.top().second;
        int time = -q.top().first;
        q.pop();

        check(pos - 1, time + 1);               // 각 3 군데를 체크
        check(pos + 1, time + 1);
        check(pos * 2, time);
    }

    cout << visited[k] << endl;
}