백준 1697번: 숨바꼭질

[문제 링크]

1697번: 숨바꼭질

---

수빈이가  위치한 좌표를 시작으로 +1 하는 경우, -1 하는 경우, *2 하는 경우 도달하는 좌표를 큐에 담는 방식으로 bfs를 수행하면 정답을 얻을 수 있다.

---

#include <iostream>
#include <queue>
using namespace std;

bool visited[100001];
int N, K;

int bfs() {
	queue<pair<int, int>> q;
	q.push({N, 0});
	visited[N] = true;

	while (!q.empty()) {
		int here = q.front().first;
		int sec = q.front().second;
		q.pop();

		if (here == K) return sec;

		sec++;
		int next = here + 1;
		if (next <= 100000 && !visited[next]) {
			q.push({ next, sec });
			visited[next] = true;
		}
		
		next = here - 1;
		if (next >= 0 && !visited[next]) {
			q.push({ next, sec });
			visited[next] = true;
		}

		next = here * 2;
		if (next <= 100000 && !visited[next]) {
			q.push({ next, sec });
			visited[next] = true;
		}
	}

	// 이 행에 도달했다면 만나는건 불가능(가능성 0%)
	return -1;
}

int main(void) {
	cin >> N >> K;

	cout << bfs() << endl;
	
	return 0;
}