[백준12851] 숨바꼭질 2 (C++)

📌 문제

BOJ 바로가기

숨바꼭질에서 조금 심화된 문제이다. 이번에는 수빈이가 동생을 찾는 데 걸리는 최소 시간뿐만 아니라 최단 경로의 개수까지 알아내야 한다.

🗡 풀이

진짜 손절하고 싶었던 문제... 왜냐면 나는 정말 맞다고 생각했는데 답이 자꾸 틀리다고 나왔다. 일일이 출력해가며 인간 디버거가 되길 자처하길 N시간째.. 겨우 문제의 원인을 찾았다.

📍 일반적인 BFS문제에서는 큐에 push할 때 visited 배열을 true로 만들어준다. 하지만 이 문제에서는 큐에서 pop할 때 visited 배열을 true로 만들어줘야 한다. 왜냐하면 최단 경로의 '개수'를 알아내야 하기 때문에, 특정 지점을 이미 한 번 방문했더라도 그 지점을 다시 방문할 수 있는 가능성을 열어둬야 하는 것이다. 또 다른 최단경로 그 지점을 거쳐 가야 할 수도 있으니까.

📍 비슷한 맥락에서 답을 찾았다고 바로 return해버리면 안 된다. 큐가 완전히 비워졌을 때 return 해주어야 한다.

🥶 나는 숨바꼭질 문제에서 dist배열을 따로 두고 큐에는 현재 위치한 지점 하나만 push했다. 그런데 이것 때문에 엄청 고생했다.. dist배열을 따로 두니까 그 지점을 다시 방문했을 때 dist값이 갱신될 여지가 있기 때문이다. 큐에 한꺼번에 {n, t}를 넣으니까 그제서야 답이 맞았다.

🚩 정답 소스코드

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

queue<pair<int, int>> q;
bool visited[100001] = { false };
int n, k, cnt = 0;
int ans;

void bfs(int n, int t) {
	q.push({ n, t });
	while (!q.empty()) {
		int n = q.front().first;
		int t = q.front().second;
		q.pop();
		visited[n] = true;
		if (n == k) {
			if (cnt == 0) {
				ans = t;
				cnt++;
			}
			else if (cnt > 0 && ans == t)
				cnt++;
		}
		int go[3] = { n - 1, n + 1, 2 * n }; // 한 칸 앞, 한 칸 뒤, 두배 점프
		for (int i = 0; i < 3; i++) {
			int nx = go[i];
			if (0 <= nx && nx <= 100000 && !visited[nx]) {
				q.push({ nx, t + 1 });
			}
		}
	}
	return;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> k;
	if (n == k) {
		cout << '0' << '\n' << '1';
	}
	else {
		bfs(n, 0);
		cout << ans << '\n' << cnt;
	}
}

🚩 오답 소스코드

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

queue<int> q;
int dist[100001] = { 0 };
bool visited[100001] = { false };
int n, k, cnt = 0;
int ans;

void bfs() {
	q.push(n);
	dist[n] = 0;
	while (!q.empty()) {
		int n = q.front();
		q.pop();
		cout << "팝" << n << "팝" << '\n';
		visited[n] = true;
		if (n == k) {
			cout << "팝" << '\n';
			if (cnt == 0) {
				ans = dist[n];
				cnt++;
			}
			else if (cnt > 0 && ans == dist[n])
				cnt++;
			return;
		}
		int go[3] = { n - 1, n + 1, 2 * n }; // 한 칸 앞, 한 칸 뒤, 두배 점프
		for (int i = 0; i < 3; i++) {
			int nx = go[i];
			if (0 <= nx && nx <= 100000 && !visited[nx]) {
				q.push(nx);
				dist[nx] = dist[n] + 1;
				cout << nx << ' ' << dist[nx] << '\n';
			}
		}
		cout << '\n';
	}
	return;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> k;
	if (n == k) {
		cout << '0' << '\n' << '1';
	}
	else {
		bfs();
		cout << ans << '\n' << cnt;
	}
}