백준 13549 - 숨바꼭질3

문제링크

• 백준 13549

문제설명

• 수빈이는 현재 점 N(0 ~ 100,000)에 있고, 동생은 점 K(0 ~ 100,000)에 있다.
• 수빈이는 걷거나 순간이동을 할 수 있다. 수빈이 위치가 X일 때, 다음과 같이 3가지 이동 방법이 있다.
  • X -> X+1 (1초 소모)
  • X -> X-1 (1초 소모)
  • X -> 2*X (0초 소모)
• 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초후인지 구하라

문제접근

• 시작지점(N)이 정해져 있고, 간선의 가중치가 0, -1, 1 로 세가지가 존재하므로 다익스트라 알고리즘을 사용하면 된다.
• time[idx] 는 idx번 위치로 이동할 때까지 걸린 시간이 담긴다. 다익스트라 알고리즘을 위해 초기값은 INF 로 설정한다.
• 이동방법은 3가지가 존재하므로, 각 3가지에 대해서 time[idx] 에 담긴 소요시간과 현재 위치에서 다음 위치로 이동할 때 걸리는 누적된 소요시간을 비교한다.
• n >= k 인 경우에는 수빈이가 동생에게 가기 위한 방법은 X->X-1 방법 밖에 없음에 유의한다.

구현

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

#define MAX 100000
#define INF 100000

int n, k;
// 최소힙 (first 기준으로 오름차순 정렬)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> time(MAX + 1, INF);

bool isValid(int x) {
	if (x<0 || x>MAX) return false;
	else return true;
}

void dijkstra() {
	time[n] = 0;
	pq.push(make_pair(0, n));
	
	while (!pq.empty()) {
		pair<int, int> cnode = pq.top();
		pq.pop();

		if (time[cnode.second] < cnode.first) continue;
		 
		// 뒤로 한칸 가는 경우
		int nextPos1 = cnode.second - 1;
		if (isValid(nextPos1) && (time[nextPos1] > cnode.first + 1)) {
			time[nextPos1] = cnode.first + 1;
			pq.push(make_pair(cnode.first + 1, nextPos1));
		}

		// 앞으로 한칸 가는 경우
		int nextPos2 = cnode.second + 1;
		if (isValid(nextPos2) && (time[nextPos2] > cnode.first + 1)) {
			time[nextPos2] = cnode.first + 1;
			pq.push(make_pair(cnode.first + 1, nextPos2));
		}

		// 순간이동
		int nextPos3 = cnode.second * 2;
		if (isValid(nextPos3) && (time[nextPos3] > cnode.first)) {
			time[nextPos3] = cnode.first;
			pq.push(make_pair(cnode.first, nextPos3));
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d", &n, &k);

	int minDist = 0;
	if (n >= k) minDist = n - k;
	else {
		dijkstra();
		minDist = time[k];
	}

	printf("%d\n", minDist);
	return 0;
}