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

다익스트라 문제.

이 문제는 처음에 BFS로 접근했는데 자꾸 틀렸습니다. 가 나왔다.

게시판을 참고하고 나서 다익스트라로 풀었다.

그런데 사람들을 보니 우선순위 큐 + BFS이면 풀 수 있다고 했다.

나도 우선순위 큐 + BFS로 시도했었는데 왜 못풀었을까..흠..

 

문제풀이

이 문제는 다익스트라로 풀어야 한다.

왜냐하면 이전의 숨바꼭질 문제들은 +1, -1, *2의 시간초과가 모두 같았지만,

이번 문제의 경우 *2가 걸리는 시간이 0초이다.

따라서 *2들 먼저 모두 탐색한 후에 또 거기서 +1, -1 *2들 먼저.. 이런식으로 탐사해야한다.

 

/*
* 백준 13549번 숨바꼭질3
* https://www.acmicpc.net/problem/13549
* 그래프 탐색 이론 - 다익스트라
* 다익스트라에서는 정점 방문을 먼저 하면 안된다. 해당 정점에 도착했을 때 정점 방문을 해야함.
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int startSubinPoint, broPoint;
int ans;
bool visit[100001];

void dijikstra() {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push({ 0, startSubinPoint });
	while (!pq.empty()) {
		int curTime = pq.top().first;
		int curPoint = pq.top().second;
		pq.pop();

		if (visit[curPoint]) { continue; }

		visit[curPoint] = true;

		if (curPoint == broPoint) {
			ans = curTime;
			return;
		}

		if (curPoint + 1 <= 100000) {
			pq.push({ curTime + 1, curPoint + 1 });
		}

		if (curPoint - 1 >= 0) {
			pq.push({ curTime + 1, curPoint - 1 });
		}

		if (curPoint * 2 <= 100000) {
			pq.push({ curTime, curPoint * 2 });
		}
	}
}

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

	cin >> startSubinPoint >> broPoint;

	dijikstra();

	cout << ans;

	return 0;
}

다익스트라로 시도했을 때, 한 번 틀렸었다.

오랜만에 풀어보는 다익스트라였는데, 다익스트라에서는 해당 정점을 큐에서 pop() 했을 때가

최소시간만에 도달했음을 의미한다.

BFS처럼 해당 정점을 큐에 넣었다고 최소시간이 보장되는 것이 아니다.

 

BFS + 우선순위 큐로 시도했었는데 계속 틀렸다.

나중에 또 봐야할 것 같다.

 

GitHub - kimyunseok/cpp: my study-record

코드는 위에서 확인 가능하다.