백준 문제 - 1697번 숨바꼭질

백준 1697번 숨바꼭질 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

수빈이는 점N(0 <= N <= 100000), 동생은 점K(0 <= K <= 100000)에 있습니다.
수빈이의 위치가 X일 때 걸어서 1초후에 X-1이나 X+1로 이동할 수 있습니다.
또는 순간이동하여 1초 후에 2*X의 위치로 이동할 수 있습니다.
수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구해야합니다.

문제 풀이

주어진 위치에서 정해진 위치까지 도달하는데 제일 빠른 방법을 찾아야 합니다.
주어진 지점부터 BFS를 사용해 이동 가능한 방법인 X-1, X+1, 2*X를 해보며 정해진 위치가 나올 때까지 반복해서 찾아내면 됩니다.
최대 100000개이므로 시간이 초과될 경우가 없을 것입니다.

여기서 시간을 조금 더 줄이는 방법이 있습니다.
만약 N = 5, K = 17이라고 주어졌을 때,
수빈이의 위치에서 시작하여 BFS를 진행하게 된다면
5
4 6 10
3 5 8 5 7 12 9 11 20
2 4 6 4 6 10....
이런식으로 진행될 것입니다.
여기서 중복되는 수를 체크하며 계산에서 제외하고, 수빈이의 위치가 아닌 동생의 위치에서 시작한다면
17
16 18 (17/2는 소수점이라 불가능함)
15 8 19 (17은 한번 검색한 부분이라 제거)
14 7 9 4 20
13 6 10 3 (5) 2 21
이런식으로 적게 탐색하여 원하는 값을 찾아낼 수 있습니다.
죽, 수빈이의 위치에서 BFS를 시작하는 것이 아닌 동생쪽부터 BFS를 시작하여 수빈이의 위치를 찾고, 중복된 값을 제거하는 방법이 더욱 빠릅니다.

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
	int n, k;
	int answer = 0;
	vector<int> checkNum(100001, 0);

	cin >> n >> k;

	queue<int> currentNum;

	currentNum.push(k);

	while (!currentNum.empty())
	{
		int qSize = currentNum.size();

		for (int i = 0; i < qSize; i++)
		{
			int num = currentNum.front();	currentNum.pop();

			if (num == n)
			{
				answer--;
				currentNum = queue<int>();
				break;
			}

			if (checkNum[num] == 0 && num >= 0)
			{
				checkNum[num] = 1;

				if (num % 2 == 0)
				{
					currentNum.push(num / 2);
				}
				currentNum.push(num - 1);
				currentNum.push(num + 1);
			}
		}
		answer++;
	}

	cout << answer;
}

출저

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