숨바꼭질 5

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.25 초	512 MB	10777	2470	1740	24.076%

문제

수빈이는 동생과 숨바꼭질을 하고 있다.

수빈이는 현재 점 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

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: dlwocks31, kravi

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

통과된 코드

문제를 해결하는 KeyPoint는 수빈이가 해당 위치에 T 초에 도달했다면 T + 2 초 후에 해당 위치에 다시 도달할 수 있다는 것이다. (+1, -1)

위와 같은 이유로 방문 배열을 홀수, 짝수로 나누어 체크해 준다.

일단 방문 배열은 -1로 전부 초기화 시켜준다. (0은 0초 때문에 사용할 수 없다.)

그 후에 모든 위치 (0 <= N <= 50,000)에 대해서 수빈이가 도착하는 최소 시간을 저장해 준다.

이때 T + 2 초 후에 해당 위치에 다시 도달할 수 있다는 것을 이용하여 BFS 탐색을 하는 경우 중복되는 CASE들을 전부 제거할 수 있다.

탐색을 완료한 후에 동생의 위치를 탐색하며 찾는 시간을 탐색하는데

만약 동생이 움직인 위치에 방문 처리가 되어있고 동생이 움직인 시간이 더 크다면 동생이 움직인 시간이 가장 빠른 시간이다.

예를 들어 X의 위치에 수빈이가 5초에 방문을 한 적이 있고 동생 그 위치에 9초에 방문을 했다면

수빈이가 +1 -1 +1 -1을 4초 동안 수행한 값이 가장 빠른 시간이라는 뜻이다.

#include <iostream>
#include <queue>
using namespace std;
constexpr auto MAX = 500001;
int _Isvisted[2][MAX]; // 홀수 짝수
queue<pair<int, int>> _BFSQueue;
pair<int, int> _CntPos;
int _N, _K, _Res;
bool _Check = false;

int main()
{
	cin >> _N >> _K;
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < MAX; j++)
			_Isvisted[i][j] = -1;

	_BFSQueue.push(make_pair(_N, 0));
	_Isvisted[0][_N] = 0;
	while (!_BFSQueue.empty()) {
		_CntPos = _BFSQueue.front();
		_BFSQueue.pop();
		int _tempPos;
		int _tempCnt = _CntPos.second + 1;
		for (int i = 0; i < 3; i++) {
			switch (i) {
				case 0:
					_tempPos = _CntPos.first - 1;
					break;
				case 1:
					_tempPos = _CntPos.first + 1;
					break;
				case 2:
					_tempPos = _CntPos.first * 2;
					break;
			}
			if (_tempPos <= -1 || _tempPos >= MAX || (_Isvisted[_tempCnt % 2][_tempPos] != -1))
				continue;
			_Isvisted[_tempCnt % 2][_tempPos] = _tempCnt;
			_BFSQueue.push(make_pair(_tempPos, _tempCnt));
		}
	}

	for (int i = 0; i <= MAX; i++) {
		_K += i;
		if (_K >= MAX) break;
		// i초 이전에 방문한 적이 있다면 i + 2초 후에 다시 방문 가능 (방문 배열을 홀, 짝으로 나눈 이유)
		if (_Isvisted[i % 2][_K] <= i && _Isvisted[i % 2][_K] != -1) {
			_Check = true;
			_Res = i;
			break;
		}
	}

	if (!_Check) cout << -1;
	else cout << _Res;

	return 0;
}