백준 1697번 숨바꼭질 (c++)

[Silver I] 숨바꼭질 - 1697

문제 링크

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

문제 설명

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

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

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int dx[3] = { 1, -1, 2 };
	int vis[200001], n, k;
	int future;
	
	cin >> n >> k;
	queue <int> Q;
	Q.push(n);
	vis[n] = 1;

	for (int i = 0; i < 200001; i++)
		vis[i] = 0;

	while (!Q.empty())
	{
		int cur = Q.front();
		if (cur == k)
		{
			cout << vis[cur];
			return 0;
		}
		Q.pop();
		for (int i = 0; i < 3; i++) {
			if (i == 2)
				future = dx[i] * cur;
			else
				future = cur + dx[i];
			if (future < 0 || future >= 200000) continue;
			if (vis[future]) continue;
			Q.push(future);
			vis[future] = vis[cur] + 1;
		}
	}
}

이 문제는 일반적으로 2차원에서 했던 BFS를 1차원에서 진행하는 방식으로 문제를 풀었다.

문제를 풀면서 어려웠던 점은 처음 풀 때는 future가 100000이 넘어가면 continue를 진행하게 풀었는데

100000이 넘어간 수에서 아래로 내려오는 방법도 있기에 vis의 크기를 200000으로 늘려서 진행하였다