[백준] 1697번. 숨바꼭질

[백준] 1697번. 숨바꼭질

1. 문제

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

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

2. 입력

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

3. 출력

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

4. 풀이

• BFS로 풀었다.
• 이미 갔던 곳이 아닌 모든 곳의 경우의 수를 구했다. BFS라 최단거리가 보장된다.

5. 처음 코드와 달라진 점

• 범위 설정에서 등호를 빼먹어서 틀렸다. 후...

6. 코드

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

int arr[100001] = { 0, };

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	int start, target;
	cin >> start >> target;
	
	queue<int> q;
	if (start != target) q.push(start);

	while (!q.empty()){
		int x = q.front();
		if (x == target) break;
		q.front();
		q.pop();
		int nx1 = x + 1;
		int nx2 = x - 1;
		int nx3 = x * 2;
		if (nx1 <= 100000 && arr[nx1] == 0) {
			q.push(nx1);
			arr[nx1] = arr[x] + 1;
		}
		if (nx2 >= 0 && arr[nx2] == 0) {
			q.push(nx2);
			arr[nx2] = arr[x] + 1;
		}
		if (nx3 <= 100000 && arr[nx3] == 0) {
			q.push(nx3);
			arr[nx3] = arr[x] + 1;
		}
	}
	cout << arr[target];
	
}