[BOJ/C++] 1697 숨바꼭질 : BFS

문제

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

풀이

계산 방식으로 풀려했는데 고려해야되는 경우도 많고, 반례도 많고... 이게 왜 BFS 문제인가 싶었는데 완전 BFS의 근본같은 문제네 ,, 머쓱

x+1 / x-1 / x*2 다 큐에 넣어주고 동생 찾을 때까지 ~.~

코드

#include <iostream>
#include <queue>

using namespace std;

int N, K;
int visited[100001];

void bfs(int node) {
	queue<pair<int, int>> q;
	q.push({ node, 0 });

	while (!q.empty()) {
		int x = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (x == K) {
			cout << cnt;
			break;
		}

		if (x + 1 >= 0 && x + 1 < 100001 && !visited[x+1]) {
			visited[x + 1] = true;
			q.push({ x + 1, cnt + 1 });
		}
		if (x - 1 >= 0 && x - 1 < 100001 && !visited[x - 1]) {
			visited[x - 1] = true;
			q.push({ x - 1, cnt + 1 });
		}
		if (x * 2 >= 0 && x * 2 < 100001 && !visited[x * 2]) {
			visited[x * 2] = true;
			q.push({ x * 2, cnt + 1 });
		}
	}
}

int main() {

	cin >> N >> K;
	visited[N] = true;
	bfs(N);

	return 0;
}