[BOJ] 18235 - 지금 만나러 갑니다

1. 문제 해석

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

18235번: 지금 만나러 갑니다

• 오리는 점 A 육리는 점 B에 위치하고 이다. 1일 차에는 1만큼 점프하고 하루가 지날 때마다 2배씩 멀리 점프한다.
• 현재 위치가 X이고 서로를 시작한 지 Y일 지났다면 X + 2^(Y-1) 또는 X - 2^(Y-1)로 점프한다.
• 0 이하 또는 N + 1 이상의 지점으로 점프할 수 없다.
• 오리와 육리가 만날 수 있는 최소 일수를 구해야 한다.

 

2. 접근방법

오리와 육리가 만나는 최소 일수를 구하는 것 이기 때문에 각각의 점프 위치를 BFS 탐색으로 기록하여 답을 구할 수 있다. 먼저 오리의 점프 위치를 저장하고 육리의 점프 위치를 기록하면서 오리가 방문했던 곳이면 같은 일수에 방문한 것인지 확인하면 된다. 또한, 오리와 육리가 만나는 최소 일수는 20일을 넘길 수 없다. 이유는 다음과 같다. 

Y일 차에 현재 위치에서 2^(Y-1)만큼 점프 가능하기 때문에 20일 차에는 524,288만큼 점프할 수 있다. N = 500,000이고 오리의 위치 A = 0, 육리의 위치 B = 500,000이라고 하면 최소 20일 전에는 둘이 만나야 한다. 그렇지 않으면 점프해야 하는 위차가 범위를 벗어난다. 

• BFS 탐색으로 오리의 점프를 기록을 visA[위치][일수]에 저장한다.
• BFS 탐색으로 육리의 점프를 기록 visB[위치][일수]에 기록하면서 오리도 같은 일수에 방문한 곳인지 확인한다.

3. 주의할 점

• 오리와 육리가 점프하여 이동하는 각 지점은 한 번 이상 방문할 수 있다.

 

4. 소스코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

const int INF = 987654321;
int N, A, B, ans = INF;
int visA[500001][20], visB[500001][20], d[2] = { -1, 1 };

void init() {
	for (int i = 0; i < 500001; i++) {
		for (int j = 0; j < 20; j++) {
			visA[i][j] = visB[i][j] = -1;
		}
	}
}

void solA() {
	queue<pair<int,int>> Q;
	visA[A][0] = 0;
	Q.push({ A, 0 });
	while (!Q.empty()) {
		int cur = Q.front().first;
		int t = Q.front().second;
		int dist = (1 << t);
		Q.pop();
		for (int k = 0; k < 2; k++) {
			int next = cur + (dist * d[k]);
			if (1 <= next && next <= N) {
				if (visA[next][t + 1] == -1) {
					visA[next][t + 1] = t + 1;
					Q.push({ next, t + 1 });
				}
			}
		}
	}
}

void solB() {
	queue<pair<int, int>> Q;
	visB[B][0] = 0;
	Q.push({ B, 0 });
	while (!Q.empty()) {
		int cur = Q.front().first;
		int t = Q.front().second;
		int dist = (1 << t);
		Q.pop();

		if (visA[cur][t] != -1 && visA[cur][t] == visB[cur][t]) {
			ans = t;
			return;
		}

		for (int k = 0; k < 2; k++) {
			int next = cur + (dist * d[k]);
			if (1 <= next && next <= N) {
				if (visB[next][t + 1] == -1) {
					visB[next][t + 1] = t + 1;
					Q.push({ next, t + 1 });
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	init();

	cin >> N >> A >> B;
	solA();
	solB();
	if (ans == INF) ans = -1;
	cout << ans << '\n';

	return 0;
}