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

숨바꼭질 3
https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

반응형

 

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

2 * X의 위치로 옮기는 경우, 0초가 걸리기 때문에 제일 첫 조건문으로 설정해주어야 합니다. (N = 1, K = 2 인 경우, 정답은 0이어야 하지만 +1 -1이 2 * X 보다 선행되어진다면 정답은 1이 될 수 있습니다.)