[백준] 13549 숨바꼭질 3 / BFS, 우선순위큐 (C++)

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

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

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

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

시행착오가 있었던 문제.
처음에는 0초 이동을 제대로 체크 못하고 기존의 문제처럼 같은 시간이 걸린다고 생각해서 문제가 됐다.
순간이동의 소요시간이 0초라는 것은 가중치가 있는 그래프라는 뜻이고,
이 가중치를 반영하기 위해 우선순위큐를 사용하기로 했다.

시간이 적게 걸리는 순으로 정렬이 되어야 빠른 시간을 구할 수 있으므로,
최소힙을 만들때 기준이 되는 first값은 시간으로 해준다. 그러면 0초 걸리는 위치를 우선적으로 탐색하게 된다.

우선순위큐를 최소힙으로 만드는 것은 이전에도 쓴 적이 있는데,
priority_queue<자료형, 컨테이너, 비교함수> 이런 식으로 넣어주면 된다.
여기에서는
pair<int, int> / vector<pair<int, int>> / greater<pair<int, int>> 의 값을 넣어주었다.

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

bool visited[100001];

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

	int N, K;
	cin >> N >> K;
	// 2배 곱하는게 시간이 0이므로 먼저 고려되어야 한다.
	// 그래서 최소힙 구현
	// 이렇게 하면 pair의 first요소를 먼저 비교한 뒤, second 요소를 비교해서 오름차순으로 정렬한다.
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pQ;
	pQ.push(make_pair(0, N));
	visited[N] = true;

	while (!pQ.empty())
	{
		int sec = pQ.top().first;
		int pos = pQ.top().second;
		pQ.pop();

		if (pos == K)
		{
			cout << sec;
			break;
		}

		if (pos*2 <  100001 && !visited[pos*2])
		{
			visited[pos * 2] = true;
			pQ.push(make_pair(sec, pos * 2));
		}
		if (pos + 1 < 100001 && !visited[pos + 1])
		{
			visited[pos + 1] = true;
			pQ.push(make_pair(sec + 1, pos + 1));
		}
		if (pos - 1 >= 0 && !visited[pos - 1])
		{
			visited[pos - 1] = true;
			pQ.push(make_pair(sec + 1, pos - 1));
		}
	}

	return 0;
}