boj-13549 숨바꼭질 3

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

문제 소개

수빈이와 동생의 위치인 N과 K가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구한다. (0 <= n, k <= 100000)

수빈이의 위치가 X라고 했을 때 수빈이는 1초 후에 X - 1 또는 X + 1로 이동하거나, 0초 후에 2 * X로 순간이동할 수 있다.

문제 풀이

BFS로 풀이하였다. 큐는 pair형 원소를 갖는데, first는 수빈이의 현재 위치이며, second는 현재 위치까지 걸린 시간을 의미한다.

vector visited로는 방문 처리를 하여 한 좌표에 중복으로 방문하는 것을 방지한다.

순간이동 시 드는 시간이 0이기 때문에, 큐에 삽입하는 세 경우 중 가장 먼저 넣는다. 그래야 n이 1이고 k가 2인 경우와 같은 반례에 걸리지 않을 수 있다.

큐에 삽입하기 위한 각 조건은 n과 k의 범위를 고려하였다. 단순 이동의 경우에는 0보다 크거나 같고 100000보다 작거나 같은 범위로 이동하도록 하였고, 순간이동의 경우에는 단순 이동을 반복하는 것보다 비용이 적은 경우에만 시행하도록 하였다.

코드

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

std::queue<std::pair<int, int>> q;
std::vector<bool> visited(200001, false);

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	// 0 <= n, k <= 100000
	int n, k;
	cin >> n >> k;

	if (n < k) {
		q.push({ n, 0 });
		visited[n] = true;
		while (!q.empty()) {
			pair<int, int> current = q.front();

			if (current.first == k) {
				cout << current.second << '\n';
				break;
			}

			q.pop();
            
            // 순간이동 후 -1씩 이동하는 것이 +1씩 이동하는 것을 반복하는 것보다 빠른 경우에만
			// 1 + (n * 2 - k) < k - n
			// 3 * n + 1 <= 2 * k
			if (3 * current.first + 1 <= 2 * k && !visited[current.first * 2]) {
				q.push({ current.first * 2, current.second });
				visited[current.first * 2] = true;
			}
			if (current.first >= 1 && !visited[current.first - 1]) {
				q.push({ current.first - 1, current.second + 1 });
				visited[current.first - 1] = true;
			}
			if (current.first < 100000 && !visited[current.first + 1]) {
				q.push({ current.first + 1, current.second + 1 });
				visited[current.first + 1] = true;
			}
		}
	}
    // n이 k보다 크거나 같은 경우에는 단순히 -1씩 이동하는 것을 반복한다.
	else {
		cout << n - k << '\n';
	}

	return 0;
}