개요

백준 13549 : 숨바꼭질 3

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

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

접근 방식

1. 처음에 다이나믹 프로그래밍방식으로 접근하였다.
   N에서 시작해 *2. +1, -1을 하고 해당 항을 전부 갱신하는 식으로 각 항을 처리했다.

2. 하지만 생각해보니 갱신된 값을 이용해 다시 갱신해야하는 경우가 발생한다.
   따라서 N부터 10만까지, 0부터 N까지 갱신을 두 번 했는데 틀리길래
   어디까지 갱신해야할까하고 무대포 정신으로 세 번째 갱신을 했더니 답이 맞았다.

3. 찾아보니 +1 , -1이 포함되므로 DP를 사용하기엔 적절하지 않은 문제라고 한다.
   싸이클이 발생하는 그래프에서는 갱신되는 상황이 발생하므로 DP를 사용하기 안 좋다고 한다.
   그냥 갱신 3번만에 답이 나오는 운이 좋았던 상황같다.

4. 따라서 N에서 K로 가는 거리 중 제일 작은 값을 찾을 수 있는 다익스트라로 풀어봤다.

5. 다익스트라의 각 루프마다 *2 , +1 , -1값을 비교해보고 갱신해주면 된다.
   다시 갱신될 수 있으므로 방문 체크는 하지않는다.

전체 코드

#include<iostream>
#include<queue>

using namespace std;

int minDist[100'002];
priority_queue<int, vector<int>, greater<int>> pq;

int main() {
	int N, K;
	fill(&minDist[0], &minDist[100'002], 111'111);
	cin >> N >> K;
	
	minDist[N] = 0;
	pq.push(N);
	while (!pq.empty()) {
		int curNode = pq.top();
		pq.pop();


		if (curNode * 2 < 100'001 && minDist[curNode * 2] > minDist[curNode]) {
			pq.push(curNode * 2);
			minDist[curNode * 2] = minDist[curNode];
		}
		if (curNode+1 <100'001&& minDist[curNode + 1] > minDist[curNode] + 1) {
			pq.push(curNode + 1);
			minDist[curNode + 1] = minDist[curNode] + 1;
		}
		if (curNode > 0 && minDist[curNode - 1] > minDist[curNode] + 1) {
			pq.push(curNode - 1);
			minDist[curNode - 1] = minDist[curNode] + 1;
		}
	}

	cout << minDist[K];

}

생각

아 이거 priority_queue 썼다가 틀려서 왜 안 되지 하고 봤더니 comparator을 Less로 사용하고 있었다..
greater로 사용하는 게 맞다..