[BOJ/C++] 13549 숨바꼭질 3 : BFS

문제

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

풀이

숨바꼭질 시리즈가 전에 풀어봤더 문제라 BFS인 거 알고, 풀었는데 큐에 x*2, x+1, x-1 넣는 순서에 따라 답이 다르게 나왔다.
전에 풀었던 문제는 전부 비용이 1이고, 이번에는 x*2인 경우에는 비용이 0이고, x+1과 x-1인 경우에는 비용이 1이라는 점에서 차이가 있다.
전에 풀이한 숨바꼭질 문제
비용을 최소로 해야 하니까 x*2를 먼저 넣는 건 알겠는데 x+1과 x-1은 넣는 순서에 따라 왜 답이 달라지는지 이것저것 시도해봤다. (if문 순서 바꿔서 정답 처리는 되었음)

• 처음에 풀이한 기본 BFS 코드

#include <iostream>
#include <queue>

using namespace std;

int n, k;
bool visited[100001];

void bfs(int node) {
	queue<pair<int, int>> q;
	q.push({ node, 0 });

	while (!q.empty()) {
		int x = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (x == k) {
			cout << cnt;
			break;
		}

		if (x * 2 >= 0 && x * 2 < 100001 && !visited[x * 2]) {
			visited[x * 2] = true;
			q.push({ x * 2, cnt });
		}
		if (x - 1 >= 0 && x - 1 < 100001 && !visited[x - 1]) {
			visited[x - 1] = true;
			q.push({ x - 1, cnt + 1 });
		}
		if (x + 1 >= 0 && x + 1 < 100001 && !visited[x + 1]) {
			visited[x + 1] = true;
			q.push({ x + 1, cnt + 1 });
		}
	}
}

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

	cin >> n >> k;
	visited[n] = true;
	bfs(n);

	return 0;
}

BFS를 하기 위해서는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요함
이 문제는 가중치가 0인 간선이 있기 때문에 일반적으로 단순한 BFS를 쓸 수는 없으나, 문제의 특성 때문에 방문 순서에 따라 단순 BFS로도 우연히 항상 정답을 찾을 수 있는 것

이 문제를 보다 일반화된 경우(가중치가 0인 간선이 있는 경우)에 대해 해결하려면, 즉, 이 문제의 의도대로 풀려면 다음과 같은 방법으로 풀이해야 함

1. 다익스트라 알고리즘
2. 0-1 BFS : 가중치가 0인 간선에연결된 정점은 큐의 맨뒤가 아닌 맨 앞에 넣는 방법 ➡️deque 또는 priority_queue 이용
3. *2를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표를 큐에 넣을 때, 그 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법

나는 priority_queue를 이용해서 최소힙을 만들어줬다. 이 때, pair 형태에서는 첫 번째 원소를 기준으로 정렬하므로 단순 BFS로 풀이했을 때와는 달리 {cost, 좌표} 형태로 큐에 넣어줬다.
그러면 x+1과 x-1의 순서에 상관없이 정답인 코드가 된다.

코드

#include <iostream>
#include <queue>

using namespace std;

int n, k;
bool visited[100001];

void bfs(int node) {
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >pq;
	pq.push({ 0, node });

	while (!pq.empty()) {
		int cnt = pq.top().first;
		int x = pq.top().second;
		pq.pop();

		if (x == k) {
			cout << cnt;
			break;
		}

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

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

	cin >> n >> k;
	visited[n] = true;
	bfs(n);

	return 0;
}