[C++] 백준 12851번: 숨바꼭질 2

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

12851번: 숨바꼭질 2

BFS를 활용한 문제다. 그런데 최소 거리를 갈 수 있는 경로의 가짓수를 알아야 하니까, 한 번 방문했다고 해서 탐색을 종료하면 안 된다. 따라서 처음 시도에서 나는 방문 체크를 하지 않고, 목적지에 도달할 때마다 해당 거리 key를 갖는 map의 한 element에 1씩 더했다. 그리고 그 key보다 거리가 더 길어질 때는 탐색을 종료하면서 연산량을 줄이려고 시도했지만, 시간초과로 실패했다. 검색을 통해 알게 된 정답은 의외로 간단했다. queue에 push할 때가 아닌 pop할 때 방문체크를 하면 된다는 것이다. 왜 그런가 생각해보니, 해당 거리가 queue에 담겨 꺼내질 시점에는 더 이상 해당 거리 이하의 값이 queue에 들어갈 수 없기 때문이다. BFS이니까. 아무튼 그런 식으로 코드를 고치고 AC를 받았다.

#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>
#define VP vector<pair<int, int>>
#define VVP vector<VP>

/* declare variables here */
int N, K;
map<int, int> ans;

/* define debug functions here */

/* define functions here */
void find() {
	queue<pair<int, int>> q;
	vector<bool> mark(100'001, false);
	q.push(make_pair(N, 0));
	while (!q.empty()) {
		auto [here, cost] = q.front();
		q.pop();
		mark[here] = true;
		if (here == K) {
			ans[cost]++;
			continue;
		}
		if (!ans.empty() && cost > (*ans.begin()).first)
			break;
		if (here * 2 <= 100'000 && !mark[here * 2])
			q.push(make_pair(here * 2, cost + 1));
		if (here + 1 <= 100'000 && !mark[here + 1])
			q.push(make_pair(here + 1, cost + 1));
		if (here - 1 >= 0 && !mark[here - 1])
			q.push(make_pair(here - 1, cost + 1));
	}
}

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

	/* Write input codes here */
	cin >> N >> K;

	/* Write solution codes here */
	find();
	cout << (*ans.begin()).first << EL << (*ans.begin()).second << EL;

	return 0;
}