[C++]BOJ 1697 - 숨바꼭질

bfs로 n + 1, n - 1, n * 2의 경우를 계속 탐색해나가며 동생의 위치에 가장 먼저 도달한 경우의 횟수를 출력하면 된다.
트리를 그려보면 알겠지만 중복되는 경우가 자주 등장해서 메모이제이션을 사용하지 않으면 메모리 초과가 뜬다.
방문을 저장할 배열 하나를 만들어준다.

#include <iostream>
#include <queue>
using namespace std;
int n, k, sn, sc, ans, v[101010];
queue<int> q, cnt;
int main() {
	cin >> n >> k;
	q.push(n), cnt.push(0);
	while(!q.empty()) {
		sn = q.front(); q.pop();
		sc = cnt.front(); cnt.pop();
		if(sn < 0 || sn > 100000) continue; if(v[sn]) continue; // runtime
		v[sn] = 1;
		if(sn == k) {
			ans = sc;
			break;
		}
		q.push(sn * 2), cnt.push(sc + 1);
		q.push(sn + 1), cnt.push(sc + 1);
		q.push(sn - 1), cnt.push(sc + 1);
	}
	cout << ans;
}