[백준 C++] 13549 숨바꼭질3

문제

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

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

입력

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

출력

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

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

풀이

시간적 여유가 충분하고 대신 메모리여유가 적을때는
최단조건을 찾기위해 우선순위큐를 사용하면 편리하다.
이 문제를 queue로 풀었을때는 2*X로 이동하는 경우와
그에 따라 BFS진행하며 너무 많은 분기가 생겨서 코드가 좀더 까다로워졌고
심지어 -1 하는것을 +1하는것보다 우선처리해야 정답코드로 나와서
아직까지 그 이유를 잘 모르겠다..
이렇듯 BFS하면서 너무 많은 분기가 생기는경우
우선순위 큐를 사용하여 그 분기중 최소인것만 우선처리 하도록 코드를 작성해보아야 겠다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using std::priority_queue; using std::vector; using std::pair; using std::greater;
typedef pair<int, int> ii;
int N, K, res = 0x7fffffff;
bool visited[100001];

void func() {
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	pq.push({ 0, N });
	visited[N] = true;
	while (!pq.empty()) {
		int t = pq.top().first;
		int n = pq.top().second;
		pq.pop();

		if (n == K) {
			res = t;
			break;
		}

		if (2 * n <= 100000 && !visited[2 * n]) {
			visited[2 * n] = true;
			pq.push({ t, 2 * n });
		}

		if (n + 1 <= 100000 && !visited[n + 1]) {
			visited[n + 1] = true;
			pq.push({ t + 1, n + 1 });
		}

		if (0 <= n - 1 && !visited[n - 1]) {
			visited[n - 1] = true;
			pq.push({ t + 1, n - 1 });
		}

	}

	printf("%d", res);
}

int main(void) {
	scanf("%d%d", &N, &K);
	func();

	return 0;
}