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

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

1697번: 숨바꼭질

 

반응형

 

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

이미 체크했던 지점을 flag로 기록하고 또다시 해당 지점에 도착하면 패스하는 방식입니다.