백준 13549번 숨바꼭질 3

문제 링크

처음에는 그리디로 접근했다가 당연히 반례가 있었다. 다음은 BFS로 접근하였는데 일반적인 BFS는 불가능하다. 왜냐하면 좌우로 이동할때는 시간(비용) 이 동일하지만 순간이동할시 비용이 0 이므로 각 간선에서의 비용이 동일하지 않다.

물론 BFS에 가지치기처럼 조건을 걸어서 문제를 풀 수도 있지만,
최소비용을 구하는 다익스트라로 접근하여 priority_queue의 Min heap을 이용하였다. 이를 이용하면 이동시마다 최소의 해로 접근시켜주기 때문에 좀 더 쉽게 코드를 짤수있다.

각각의 if문을 돌 때, MAX값을 넘지 않도록 하며, 전으로 돌아갈때는 음수값이 나오지않도록 생각하여야한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n, k;
bool visited[100001];
int dijkstra() {
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> >pq;
	pq.push({ 0,n });
	visited[n] = true;
	while (!pq.empty()) {
		int time = pq.top().first;
		int now = pq.top().second;

		pq.pop();

		if (now == k) return time;

		if (2*now < 100001 && !visited[2*now]) {
			visited[2 * now] = true;
			pq.push({time,2 * now });

		}
		if (now-1 >= 0 && !visited[now - 1]) {
			visited[now - 1] = true;
			pq.push({ time + 1,now - 1 });
		}
		if (now+1 < 100001 && !visited[now + 1]) {
			visited[now + 1] = true;
			pq.push({ time + 1,now + 1 });
		}
	}


}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> k;
	
	cout << dijkstra();

	
	return 0;
}