[백준/c++] BOJ 13913 - 숨바꼭질 4

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

13913번: 숨바꼭질 4

 

문제 설명

수빈이는 현재 점 N에 있고, 동생은 점 M에 있다.

수빈이의 위치가 X일 때, X + 1, X - 1, X * 2의 위치로 이동할 수 있다.

이동할 때에는 1초가 걸리며, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구한다.

또한, 어떻게 이동해야 하는지 경로를 출력한다.

N, M (1 <= N, M <= 100,000)

 

해결

간단한 BFS에 경로 출력이 더해진 문제이다.

 

최단 거리는 BFS를 통해 구해 준다.

BFS를 통해 거리를 찾을 때, parent 배열에 어디 숫자로부터 도착했는지 각각 저장해 준다.

동생의 위치에 도달했을 때 parent배열을 동생의 위치부터 수빈이의 위치까지 역추적하며 vector에 경로를 저장한다.

 

N과 M이 같을 때와, N이 M보다 더 클 때는 예외처리 해 주었다.

N이 M보다 클 때는 수빈이가 X - 1의 연산으로밖에 이동할 수 없으므로 따로 예외처리 해 주어 더 빠른 시간 내로 도달할 수 있도록 하였다.

 

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m;
int visited[200002];
int parent[200002];
vector<int> v;

void bfs() {
	queue<int> q;
	q.push(n);
	visited[n] = 1;

	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (auto a : { cur + 1, cur - 1, cur * 2 }) {
			if (a < 0 || a > 200005) continue;
			if (visited[a]) continue;

			visited[a] = visited[cur] + 1;
			parent[a] = cur;
		
			if (a == m) {
				int idx = a;
				for (int i = 0; i < visited[a]; i++) {
					v.push_back(idx);
					idx = parent[idx];
				}
				return;
			}
			q.push(a);
		}
	}
}

 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;

	if (n == m) {
		cout << 0 << "\n" << n;
		return 0;
	}
	if (m < n) {
		cout << n - m << "\n";
		for (int i = n; i >= m; i--)
			cout << i << " ";
		return 0;
	}

	bfs();
	cout << visited[m] - 1 << "\n";

	for (int i = v.size() - 1; i >= 0; i--)
		cout << v[i] << " ";

}