[BOJ/Gold 1] 백준 17071 숨바꼭질 5(C++)

문제 링크

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

17071번: 숨바꼭질 5

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

입력

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

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

예제 입력 1

5 17

예제 출력 1

2

예제 입력 2

17 5

예제 출력 2

4

예제 입력 3

6 6

예제 출력 3

0

예제 입력 4

1 500000

예제 출력 4

-1

예제 입력 5

250000 499999

예제 출력 5

1

예제 입력 6

1 10

예제 출력 6

6

알고리즘 분류

• 그래프 탐색

풀이

짝수 홀수시간에 따라 수빈이와 동생이 만날 수 있는 곳을 찾는다.

우선 visited[2][500001]의 방문 표시 배열을 선언하고, 짝수 시간에 N에 방문했다면 visited[0][N]에 시간을, 홀수 시간에 N을 방문했다면 visited[1][N]에 시간을 저장하고 위치와 시간 정보를 큐에 넣는다.

BFS 탐색 도중 위치가 음수가 되거나 50만이 넘는 경우는 큐에 넣지 않는다.

그리고 0초부터 반복문을 돌려, 수빈이가 i초의 동생의 위치에 방문했는데, 둘 다 짝수 시간에 방문했거나 홀수 시간에 방문하고, 수빈이가 동생보다 해당 위치를 먼저 방문했다면 i초에 동생과 만날 수 있다는 뜻이므로 i를 출력하고, 동생의 위치가 50만이 넘어가는데도 수빈이가 동생과 만나지 못 했다면 실패한 것이므로 -1을 출력한다.

코드

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

using namespace std;
struct INFO {
	int N, Cost;
};

int N, K;
int visited[2][MAX];

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

void BFS() {
	queue<INFO> Q;
	INFO Info = { N,0 };
	visited[0][N] = 0;
	Q.push(Info);

	while (!Q.empty()) {
		INFO CurInfo = Q.front();
		Q.pop();

		// 수빈이가 왼쪽으로 걸음
		int nextN = CurInfo.N - 1;
		if ((nextN <= 500000) && (nextN >= 0) && (visited[(CurInfo.Cost + 1) % 2][nextN] == -1)) {
			visited[(CurInfo.Cost + 1) % 2][nextN] = CurInfo.Cost + 1;
			INFO newInfo = { nextN,CurInfo.Cost + 1 };
			Q.push(newInfo);
		}

		// 수빈이가 오른쪽으로 걸음
		nextN = CurInfo.N + 1;
		if ((nextN <= 500000) && (nextN >= 0) && (visited[(CurInfo.Cost + 1) % 2][nextN] == -1)) {
			visited[(CurInfo.Cost + 1) % 2][nextN] = CurInfo.Cost + 1;
			INFO newInfo = { nextN,CurInfo.Cost + 1 };
			Q.push(newInfo);
		}

		// 수빈이가 순간이동함
		nextN = CurInfo.N * 2;
		if ((nextN <= 500000) && (nextN >= 0) && (visited[(CurInfo.Cost + 1) % 2][nextN] == -1)) {
			visited[(CurInfo.Cost + 1) % 2][nextN] = CurInfo.Cost + 1;
			INFO newInfo = { nextN,CurInfo.Cost + 1 };
			Q.push(newInfo);
		}
	};
}

int Can_Find() {
	int CurK = K;
	for (int i = 0; i <= 500000; i++) {
		CurK += i;
		if (CurK > 500000) {
			break;
		}
		if ((visited[i % 2][CurK] != -1) && (visited[i % 2][CurK] <= i)) {
			return i;
		}
	}
	return -1;
}

int main() {
	FIRST
	init();
	cin >> N >> K;
	BFS();
	cout << Can_Find() << "\n";

	return 0;
}