[c++] 백준 17071, 숨바꼭질 5

백준 17071

🌲 문제 요약

정해진 규칙에 따라 이동하는 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 문제.

🌲 문제 풀이

큐 q에 수빈이의 위치를 반복적으로 push해 나가며, 수빈이의 위치와 동생의 위치를 확인한다.
배열 visited에는 turn과 수빈이의 위치를 저장하며, 만일 visited[turn % 2][k]의 값이 존재한다면 ok에 1을 저장하고 break한다. 마찬가지로 nx == k를 만족한다면 ok에 1을 저장하고 break한다.
ok의 값이 1이라면 turn을, 0이라면 -1을 출력한다.

🌲 주의

수빈이와 동생이 같은 지점에 다른 turn에 도착하였더라도, turn의 홀짝 여부가 일치한다면 둘은 서로 만날 수 있다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
const int MAX = 500000;
int n, k, ok, visited[2][MAX + 5], turn = 1;
queue<int> q;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	if (n == k) {
		cout << 0 << '\n';
		return 0;
	}
	visited[0][n] = 1;
	q.push(n);
	while (1) {
		k += turn;
		if (k > MAX) break;
		if (visited[turn % 2][k]) {
			ok = 1;
			break;
		}
		int qSize = q.size();
		for (int i = 0; i < qSize; i++) {
			int x = q.front(); q.pop();
			for (int nx: {x - 1, x + 1, x * 2}) {
				if (nx < 0 || nx > MAX || visited[turn % 2][nx]) continue;
				visited[turn % 2][nx] = 1;
				if (nx == k) {
					ok = 1;
					break;
				}
				q.push(nx);
			}
			if (ok) break;
		}
		if (ok) break;
		turn++;
	}
	if (ok) cout << turn << '\n';
	else cout << -1 << '\n';
	
	return 0;
}