1. 문제설명

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

2. 알고리즘 설계

이전 숨바꼭질 문제에 대비해 시간 제한이 0.25초로 줄어들었다.
또한 동생이 매초마다 이동을 하기 때문에 만나지 못하는 경우가 생길 수 있다.
이 문제는 일반적인 BFS 접근으로는 해결할 수 없었다.
- 수빈이가 짝수초에 접근한 위치는 짝수초에 또 방문할 수 있다.
- 마찬가지로 홀수초에 접근한 위치는 홀수초에 또 방문할 수 있다.
- 따라서 다음과 같이 2차원 배열로 최초 방문 시간을 체크 해준다
  - visited[SZ + 1][2]
  - 0번째 위치는 짝수초, 1번째 위치는 홀수초 방문을 의미
동생의 이동시간은 현재 수빈이가 소모한 시간(time)으로 계산가능하다.
- K + time * (time + 1) / 2

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int n, k;
const int SZ = 500000;
bool visited[SZ + 1][2];


int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> k;

	queue<pii> q;

	q.push({ n, 0 });
	visited[n][0] = true;

	while (!q.empty()) {
		pii cur = q.front();
		q.pop();

		int now = cur.first;
		int time = cur.second;
		int pos = k + time * (time + 1) / 2;

		if (pos > SZ) {
			cout << -1;
			return 0;
		}

		if (now == pos || visited[pos][time % 2]) {
			cout << time;
			return 0;
		}

		for (int next : {now - 1, now + 1, 2 * now}) {
			if (next >= 0 && next <= 500000 && !visited[next][(time + 1) % 2])
			{
				q.push({ next,time + 1 });
				visited[next][(time + 1) % 2] = true;
			}
		}
		
	}

	return 0;
}

4. 소감

진짜 역대급 난이도의 BFS 문제였다.
- 구현 난이도보다는 사고력을 요구했달까
추가로, 매우 아름다운 구현법을 발견했다.
- for (int next : {now - 1, now + 1, 2 * now})
- 기존에는 next를 일일히 초기화 시켜줬다면,
- 이 방법은 한줄로 여러 코드를 재작성하지 않아도 된다!

BOJ 17071. 숨바꼭질 5

1. 문제설명

2. 알고리즘 설계

3. 전체 코드

4. 소감