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

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

13549번: 숨바꼭질 3

---

SOLUTION

숨바꼭질 문제와는 다르게 순간이동 하는 경우에 0초가 걸리기 때문에, 우선순위 큐를 사용해서 순간이동을 맨 앞으로 넣어서 너비 우선 탐색을 진행한다.

---

코드

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

int n, k;
int visited[100001];

void bfs(int n, int k) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
	pq.push({ 0,n });
	visited[n] = 1;
	while (!pq.empty()) {
		int cnt = pq.top().first;
		int num = pq.top().second;
		pq.pop();
		if (num == k) {
			cout << cnt;
			return;
		}
		if (num * 2 < 100001 && !visited[num * 2]) {
			visited[num * 2] = 1;
			pq.push({ cnt, num * 2 });
		}
		if (num - 1 >= 0 && !visited[num - 1]) {
			visited[num - 1] = 1;
			pq.push({ cnt + 1, num - 1 });
		}
		if (num + 1 < 100001 && !visited[num + 1]) {
			visited[num + 1] = 1;
			pq.push({ cnt + 1, num + 1 });
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin >> n >> k;
	bfs(n, k);
}