백준 13913번: 숨바꼭질 4

[문제 링크]

13913번: 숨바꼭질 4

---

간단한 bfs 문제였다.

수빈이가 +1, -1로 이동하는 경우와, *2로 이동하는 경우에 대해서 bfs를 돌려서 동생을 찾는 가장 빠른 방법을 찾으면 된다.

수빈이가 이동하는 경로를 저장하기 위해 queue에 현재 위치와 그동안 이동했던 경로를 담은 queue를 pair 자료구조에 담았다.

 

한가지 함정이 있다면, 수빈이가 동생보다 앞에 있을 경우, +1과 *2로 이동하게 되면 반드시 더 멀어지게 되기 때문에 -1로만 이동하게 된다.

극단적인 예로 만약 수빈이가 100000에 위치해 있고, 동생이 0에 위치해 있는 경우 수빈이의 이동경로는 100000 99999 99998 .... 0 이 된다. 이 경로를 queue에 전부 담게 되면 시간복잡도 및 공간복잡도가 매우 커지게 된다.

따라서 시작지점이 수빈이가 동생보다 앞일 경우, bfs를 수행하지 않고 -1로 이동하는 경로를 출력하도록 구현하였다.

---

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

bool visited[100001];

queue<int> bfs(int N, int K) {
	queue < pair<int, queue<int>>> q;
	q.push({ N, queue<int>({N}) });
	visited[N] = true;

	while (!q.empty()) {
		int here = q.front().first;
		queue<int> route = q.front().second;
		q.pop();

		if (here == K) return route;

		for (int i = 0; i < 3; i++) {
			int next;
			if (i == 0) next = here + 1;
			else if (i == 1) next = here - 1;
			else next = here * 2;

			if (next >= 0 && next <= 100000 && !visited[next]) {
				queue<int> temp = route;
				temp.push(next);
				q.push({ next, temp });
				visited[next] = true;
			}
		}
	}

	return queue<int>();
}

int main(void) {
	int N, K;
	cin >> N >> K;

	if (N >= K) {
		cout << N - K << endl;
		while (N >= K)
			cout << N-- << ' ';
	}
	else {
		queue<int> result = bfs(N, K);

		cout << result.size() - 1 << endl;
		while (!result.empty()) {
			cout << result.front() << ' ';
			result.pop();
		}
	}

	return 0;
}