[백준] 13549번. 숨바꼭질 3

[백준] 13549번. 숨바꼭질 3

1. 문제

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

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

2. 입력

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

3. 출력

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

4. 풀이

• [백준] 1697번. 숨바꼭질 문제와 유사하다.
• 다만, 순간이동할 때 시간을 소모하지 않는다는 것만 다르다.
• 순간이동을 할 때가 가장 최소 시간이기 때문에 항상 순간이동을 가장 먼저 해준다.
• 나머지 코드는 1697번. 숨바꼭질 코드를 그대로 사용했다.
• 다만, 1697번을 풀 때는 visited배열을 따로 만들어 주지 않고 배열의 값이 0인지 아닌지로 판단했지만 이번엔 시간이 0인 경우가 생기기 때문에 visited배열을 따로 만들어 주었다.

5. 처음 코드와 달라진 점

• visited배열까지 잘 만들어 놓고 nx2와 nx3에 적용하지 않았다.
  근데 심지어 채점이 어느정도까지 잘 됐다.

6. 코드

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

int arr[100001] = { 0, };
bool visited[100001];

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 * 2;
		int nx2 = x - 1;
		int nx3 = x + 1;
		if (nx1 <= 100000 && !visited[nx1]) {
			q.push(nx1);
			visited[nx1] = true;
			arr[nx1] = arr[x];
		}
		if (nx2 >= 0 && !visited[nx2]) {
			q.push(nx2);
			visited[nx2] = true;
			arr[nx2] = arr[x] + 1;
		}
		if (nx3 <= 100000 && !visited[nx3]) {
			q.push(nx3);
			visited[nx3] = true;
			arr[nx3] = arr[x] + 1;
		}
	}
	cout << arr[target];

}