[백준] 13913 숨바꼭질 4

문제

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

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

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1}, INF = 987654321;

using namespace std;

int N, K, v[200001], p[200001];
int main() {
	FAST;
	cin >> N >> K;
	if (N == K) {
		cout << 0 << "\n" << N;
		return 0;
	}
	queue<int>q;
	q.push(N);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		vi temp;
		temp.push_back(cur - 1);
		temp.push_back(cur + 1);
		temp.push_back(cur * 2);

		for (int r : temp) {
			if (r >= 0 && r <= 200000 && !v[r]) {
				p[r] = cur;
				v[r] = v[cur] + 1;
				q.push(r);
				vi ans;
				if (r == K) {
					cout << v[r] << "\n";
					for(int i=r;i!=N;i=p[i]){
						ans.push_back(i);
					}
					cout << N << " ";
					for (int i = ans.size() - 1; i >= 0; i--) {
						cout << ans[i] << " ";
					}
					return 0;
				}
			}
		}
	}
}

 

BFS문제입니다.

최소 시간을 찾았을때 경로는 배열 p에 저장합니다

배열 p는 이전에 몇번째 노드를 방문했는지 저장합니다.

for(i=목적지 ; i!=출발지 ; i=p[i])

를 이용해 목적지에서 출발지까지 이동경로를 찾습니다.

 

최대유량문제에서 흐르는 경로를 찾는 방법과 같습니다.