[백준 13549번] 숨바꼭질3 / C++ 다익스트라

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

풀이

수빈이가 이동할 수 있는 경우의 수가 3개이기 때문에 당연히 bfs를 적용해서 풀어야 된다고 생각했다.

하지만 4%에서 틀렸습니다를 만나게 됐고 깊은 고민에 빠졌다..

혼자 생각해보다가 모르겠어서 질문 게시판을 열심히 뒤져봤다.

그리고 알게 된 너무너무 당연하고 충격적인 사실!!

bfs는 가중치가 같은 그래프에서 적용하는 알고리즘이다.

지금처럼 가중치가 다를 경우에는 다익스트라를 적용해야된다.

나는 바보인가..이래서 알고리즘은 기본 개념이 제일 중요한 것이다..

기본을 잘 다져야...문제에 맞는 알고리즘을 고를 수 있고..구현할 수 있는 거다..

잘하자....기본을..다지자..^^..!!

아무튼 다익스트라를 적용하면 문제를 쉽게 풀 수 있다!!

(나는 bfs를 구현할 때 선언해놓은 조건때문에 이후로도 틀렸습니다를 6번은 더 만나야 했다..^^ㅎ)

코드는 다음과 같다

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define MAX 100001
#define INF 1e9

int K;
// 다익스트라 구현
int dijkstra(int start)
{
    priority_queue<pair<int, int>> needVisit;
    int minTime[MAX];
    needVisit.push({0, start});
    fill(minTime, minTime + MAX, INF);
    minTime[start] = 0;

    while (!needVisit.empty())
    {
        int time = -needVisit.top().first;
        int current = needVisit.top().second;
        // 현재 지점에서 갈 수 있는 곳들 저장
        int next[3] = {current - 1, current + 1, current * 2};
        needVisit.pop();
        if (time > minTime[current])
        {
            continue;
        }
        for (int i = 0; i < 3; i++)
        {
            // 순간이동 할 때는 시간이 증가되지 않기 때문에 다음과 같이 변수 선언
            int nextTime = i == 2 ? time : time + 1;
            if (next[i] < 0 || next[i] >= MAX || nextTime >= minTime[next[i]])
            {
                continue;
            }
            minTime[next[i]] = nextTime;
            needVisit.push({-nextTime, next[i]});
        }
    }
    return minTime[K];
}

int main(void)
{
    int N;
    cin >> N >> K;

    cout << dijkstra(N);
    return 0;
}