문제 출처

1. 문제설명

  • 수빈이는 N, 동생은 K에 위치해있다.
  • 수빈이는 위치 X에서 X-1, X+1, 2*X 위치로 이동할 수 있다.
    • 이동할 때마다 1초의 시간이 소요된다.
  • 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하라.
  • 다음 줄에는 이동한 경로를 출력하라.



2. 알고리즘 설계

  • BFS 문제이다.
  • 방문했던 노드의 부모 노드를 저장하는 배열을 추가했다.



3. 로직

  • BFS 구현은 3단계로 나뉜다.
    • 앞서 문제에 제시된 3가지 이동 경우
  • 범위를 벗어나지 않으면, 큐에 넣어준다.
  • 이 때, visited를 갱신하면서 부모 노드 배열 또한 갱신한다.
  • 목적지에 도착했다면, 벡터에 경로를 저장한다.
    • 부모 노드가 N이 아닐 때까지 추가한다.
    • 시작 노드는 무조건 N이므로, N을 추가한다.
  • 벡터의 마지막 부분부터 출력해주면 된다.
    • 참고로, 예제의 답은 여러 개 가능하다.
    • 큐에 넣는 순서에 따라 값이 달라지기 때문이다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int n, k;
const int SZ = 100000;
bool visited[SZ + 1];
int parent[SZ + 1];
vector<int> path;

typedef struct {
	int x, w;
}Pos;

int bfs() {
	queue<Pos> q;
	q.push({ n, 0 });
	visited[n] = 1;

	while (!q.empty()) {
		Pos cur = q.front();
		q.pop();

		if (cur.x == k) {
			int idx = cur.x;
			while (idx != n) {
				path.push_back(idx);
				idx = parent[idx];
			}
			path.push_back(n);

			return cur.w;
		}

		int nx = cur.x + 1;
		if (nx <= SZ && !visited[nx]) {
			q.push({ nx, cur.w + 1 });
			visited[cur.x + 1] = true;
			parent[nx] = cur.x;
		}

		nx = cur.x - 1;
		if (nx >= 0 && !visited[nx]) {
			q.push({ nx, cur.w + 1 });
			visited[nx] = true;
			parent[nx] = cur.x;
		}

		nx = cur.x * 2;
		if (nx <= SZ && !visited[nx]) {
			q.push({ nx, cur.w + 1 });
			visited[nx] = true;
			parent[nx] = cur.x;
		}
	}

	return -1;
}

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

	cin >> n >> k;
	cout << bfs() << '\n';

	for (int i = path.size() - 1; i >= 0; i--) cout << path[i] << ' ';
	return 0;
}