백준 13913: 숨바꼭질 4

문제 요약

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

단순히 BFS를 구현하여 탐색하는 문제는 맞지만, 몇 가지 함정이 숨어있다.
우선 k에 도착하였을때 탐색 순서를 알아야 하므로 큐의 원소는 pair<int, vector<int>>로 놓는다. first가 현재 위치이고, second가 탐색한 숫자를 순차적으로 나열한 vector이다.

두 번째 함정은 k < n일 경우이다. 결국 n은 작아지려면 n - 1로 이동하는 방법밖에 없기 때문에, 따로 골라내줘서 출력해줘야한다. n - k의 최댓값은 100,000이다. n * 2나 n + 1을 병행하여서 똑같이 BFS할 경우 탐색 시간은 급격히 늘어나게 된다.

이 두 가지 경우만 파악한다면 어렵지 않다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

bool visited[100001];

int main()
{
	int n, k, level = -1, qsize;
	bool solve = false;
	queue<pair<int, vector<int>>> q;
	cin >> n >> k;
	if (n > k) {
		printf("%d\n", n - k);
		while (n >= k)
			printf("%d ", n--);
		return 0;
	}
	vector<int> v;
	q.push({ n, {n} });
	visited[n] = true;
	while (!q.empty()) {
		level++;
		qsize = q.size();
		while (qsize--) {
			auto& r = q.front();
			n = r.first;
			v = r.second;
			q.pop();
			if (n == k) {
				solve = true;
				break;
			}
			if (n * 2 < 100001) {
				if (!visited[n * 2]) {
					v.push_back(n * 2);
					q.push({ n * 2 , v });
					v.pop_back();
					visited[n * 2] = true;
				}
			}
			if (n + 1 <= k) {
				if (!visited[n + 1]) {
					v.push_back(n + 1);
					q.push({ n + 1, v });
					v.pop_back();
					visited[n + 1] = true;
				}
			}
			if (n - 1 >= 0) {
				if (!visited[n - 1]) {
					v.push_back(n - 1);
					q.push({ n - 1 , v });
					v.pop_back();
					visited[n - 1] = true;
				}
			}
		}
		if (solve) break;
	}
	printf("%d\n", level);
	for (auto it : v)
		printf("%d ", it);
	return 0;
}