숨바꼭질 4 (feat. 백준, 13913번)

숨바꼭질 4
https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
pair<int, int> dp[100001];
bool visit[100001];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	memset(visit, false, sizeof(visit));
	register int N, K;
	cin >> N >> K;
	dp[N] = make_pair(-1, 0);
	queue<int> q;
	q.push(N);
	visit[N] = true;
	while (!q.empty()) {
		auto v = q.front(); q.pop();
		if (v == K)
			break;
		if (v - 1 >= 0 && !visit[v - 1])
			visit[v - 1] = true, dp[v - 1].first = v, dp[v - 1].second = dp[v].second + 1, q.push(v - 1);
		if (v + 1 <= 100000 && !visit[v + 1])
			visit[v + 1] = true, dp[v + 1].first = v, dp[v + 1].second = dp[v].second + 1, q.push(v + 1);
		if (v << 1 <= 100000 && !visit[v << 1])
			visit[v << 1] = true, dp[v << 1].first = v, dp[v << 1].second = dp[v].second + 1, q.push(v << 1);
	}
	cout << dp[K].second << "\n";
	stack<int> ans;
	while (1) {
		ans.push(K);
		K = dp[K].first;
		if (K < 0)
			break;
	}
	while (!ans.empty())
		cout << ans.top() << " ", ans.pop();
	return 0;
}
// *&)*@*

1. 이전 '숨바꼭질' 문제에서 어떤 위치를 거쳐왔는지를 기록했습니다.
2. 즉, 기존 dp[N] = 0 을 시작으로 dp[N - 1] = dp[N] + 1, dp[N + 1] = dp[N] + 1, dp[N * 2] = dp[N] + 1 의 과정과 더불어 dp[N-1] = N, dp[N + 1] = N, dp[N * 2] = N 과 같이 어떤 위치를 거쳐왔는지를 기록하는 방법입니다.
3. '숨바꼭질' 문제를 풀지 않으셨다면 선행하시길 권장합니다.

숨바꼭질 (feat. 백준, 1697번)