[BOJ/Gold 3] 백준 18235 지금 만나러 갑니다(C++)

문제 링크

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

18235번: 지금 만나러 갑니다

문제

여행을 마치고 꽉꽉나라로 돌아가던 중 오리와 육리는 서로를 잃어버렸다. 현재 오리는 점 A에 있고, 육리는 점 B에 있다.

오리와 육리는 서로를 찾기 위해 무조건 하루에 한 번씩 점프를 한다. 1일차에는 1만큼 점프하고 하루가 지날 때마다 서로가 더욱 보고 싶은 나머지 두 배씩 더 멀리 점프한다. 즉, 현재 위치가 X이고 서로를 찾기 시작한 지 y일차라면 점 X + 2y^-1 또는 점 X - 2y^-1로 점프한다. 0 이하의 점들과 N+1 이상의 점들은 디딜 땅이 없기 때문에 그곳으로 점프한다면 오리와 육리는 영원히 만나지 못한다.

아래 그림은 N = 10, A = 4, B = 10일 때의 예시이다. 화살표는 점프 가능한 위치를 나타낸다.

오리와 육리의 위치가 주어졌을 때, 둘이 만날 수 있는 최소 일수를 구해보자. 같은 날 같은 점의 땅에 도착했을 때 오리와 육리가 만난 것으로 간주한다.

입력

첫 번째 줄에 세 정수 N, A, B가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ A, B ≤ N, A ≠ B)

출력

첫 번째 줄에 오리와 육리가 만날 수 있는 최소 일수를 출력한다. 만약 오리와 육리가 영원히 만날 수 없다면 -1을 출력한다.

예제 입력 1

10 4 10

예제 출력 1

2

위에서 설명한 예시이다.

예제 입력 2

2 1 2

예제 출력 2

-1

1일차에 오리는 점 2로, 육리는 점 1로 점프한다. 2일차부터는 오리와 육리가 점프를 해야 하지만 점프 후에 디딜 수 있는 땅이 없어 영원히 만날 수 없다.

예제 입력 3

7 2 6

예제 출력 3

2

알고리즘 분류

• 그래프 탐색

풀이

일단 오리를 BFS로 이동시키면서 몇일에 어디로 이동했는지를 기록한다.

그리고 육리를 BFS로 이동시키면서 CurX 위치에 CurDay 일에 오리 역시 도달했던 기록이 있다면 CurDay를 출력하고, 없다면 -1을 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 500005
#define LL long long
#define INF 2e9

using namespace std;
int N, A, B;
int visitedA[MAX][21];
int visitedB[MAX][21];

void init() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < 21; j++) {
			visitedA[i][j] = -1;
			visitedB[i][j] = -1;
		}
	}
}

void BFS_A() {
	queue<pair<int, int> > Q;
	visitedA[A][0] = 0;
	Q.push(make_pair(A, 0));

	while (!Q.empty()) {
		int CurX = Q.front().first;
		int CurDay = Q.front().second;
		Q.pop();

		int nextX;
		// 왼쪽으로 이동
		nextX = CurX - (int)pow(2, CurDay);
		if ((nextX >= 1) && (nextX <= N) && (visitedA[nextX][CurDay + 1] == -1)) {
			visitedA[nextX][CurDay + 1] = CurDay + 1;
			Q.push(make_pair(nextX, CurDay + 1));
		}

		// 오른쪽으로 이동
		nextX = CurX + (int)pow(2, CurDay);
		if ((nextX >= 1) && (nextX <= N) && (visitedA[nextX][CurDay + 1] == -1)) {
			visitedA[nextX][CurDay + 1] = CurDay + 1;
			Q.push(make_pair(nextX, CurDay + 1));
		}
	};
}

int BFS_B() {
	queue<pair<int, int> > Q;
	visitedA[B][0] = 0;
	Q.push(make_pair(B, 0));

	while (!Q.empty()) {
		int CurX = Q.front().first;
		int CurDay = Q.front().second;
		Q.pop();

		if ((visitedA[CurX][CurDay] != -1) && (visitedA[CurX][CurDay] == visitedB[CurX][CurDay])) {
			return CurDay;
		}

		int nextX;
		// 왼쪽으로 이동
		nextX = CurX - (int)pow(2, CurDay);
		if ((nextX >= 1) && (nextX <= N) && (visitedB[nextX][CurDay + 1] == -1)) {
			visitedB[nextX][CurDay + 1] = CurDay + 1;
			Q.push(make_pair(nextX, CurDay + 1));
		}

		// 오른쪽으로 이동
		nextX = CurX + (int)pow(2, CurDay);
		if ((nextX >= 1) && (nextX <= N) && (visitedB[nextX][CurDay + 1] == -1)) {
			visitedB[nextX][CurDay + 1] = CurDay + 1;
			Q.push(make_pair(nextX, CurDay + 1));
		}
	};

	return -1;
}

int main() {
	FIRST
	init();
	cin >> N >> A >> B;
	BFS_A();
	cout << BFS_B() << "\n";

	return 0;
}