[백준] 1697 - 숨바꼭질 (C++)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

코드

using namespace std;

int bfs(int start, int target) {
	queue<int> q;
	set<int> visited; 
	vector<int> level(100001); //0으로 초기화 
	q.push(start);
	level[start] = 1;

	while (!q.empty()) {
		int node = q.front();
		q.pop(); //pop이 반환 x
		if (node == target) return level[target];
		if (!visited.count(node)) {
			visited.insert(node);
			vector<int> nexts = { node * 2, node - 1, node + 1 };
			for (int next : nexts) {
				if (next >= 0 && next <= 100000 && !level[next]) {
					q.push(next);
					level[next] = level[node] + 1;
			}
			}

		}
	}
	return 0;

}

int main(void) {
	int n;
	int m;
	cin >> n;
	cin >> m;
	int ans = bfs(n, m);
	cout << ans - 1;


	return 0;
}

풀이 및 생각

처음에는 어떠한 점화식이 있을 것이라고 생각했다. 그러나 시작점과 끝점이 정해져 있고, 인접한 노드의 수가 모두 3개(n+1, n-1, n*2) 고정되어 있어 BFS로 구현하였다.
이번 문제는 bfs의 level을 구하는 것이 목표였다. 따라서 새로운 vetor를 만들어 각각의 인덱스를 node로 하여 level을 저장했다. 이후 새롭게 queue에 저장되는 node들은 기존 node의 level보다 1 큰 level을 가지게 된다.

오랜만에 풀어서 그런지 처음에 stack으로 헷갈렸는데 bfs는 먼저 들어온 node부터 탐색해야 한다. 따라서 queue를 사용하는 게 맞다.

방문해야 하는 노드들은

vector<int> nexts = { node * 2, node - 1, node + 1 };

다음과 같이 vector에 저장하여 it로 사용했다.