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

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

13549번: 숨바꼭질 3

과거에 이 문제와 유사한 문제를 풀어본 적이 있다.

이 문제는 일반적인 Queue를 사용하는 BFS가 아닌 Priority Queue를 사용해야 한다.

시간이 짧을 수록 먼저 계산돼야 하기 때문이다.

이 문제에 대한 답안을 제출하면서 여러 번 AC를 못 받았는데,

처음에는 Priority Queue를 안 썼고

두 번째에는 +를 -로 적는 오타가 있었고

세, 네번째에는 방문 체크 bool 배열을 끝까지 초기화하지 않았다.

주의깊게 코드를 작성, 검토하고 제출하는 습관을 들여야겠다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, K;
	cin >> N >> K;

	int min_cost = INF;
	bool mark[100'001];
	memset(mark, false, sizeof(bool) * 100'001);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> bfs;
	bfs.push(make_pair(0, N));
	mark[N] = true;
	while (!bfs.empty()) {
		auto [cost, p] = bfs.top();
		bfs.pop();
		if (p == K) {
			min_cost = cost;
			break;
		}
		if (p * 2 <= 100'000 && !mark[p * 2]) {
			bfs.push(make_pair(cost, p * 2));
			mark[p * 2] = true;
		}
		if (p + 1 <= 100'000 && !mark[p + 1]) {
			bfs.push(make_pair(cost + 1, p + 1));
			mark[p + 1] = true;
		}
		if (p - 1 >= 0 && !mark[p - 1]) {
			bfs.push(make_pair(cost + 1, p - 1));
			mark[p - 1] = true;
		}
	}

	cout << min_cost << EL;

	return 0;
}