1. 문제

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

수빈이의 위치가 N일 때 1초 동안 N-1, N+1, N*2 로 이동할 수 있다.
수빈이의 위치를 N, 그리고 동생의 위치가 K일 때 가장 빠르게 동생을 찾는 시간과 그 가짓수를 구하라.

숨바꼭질 1 문제에서는 가장 빠른 시간만을 찾는거 였다면 2에서는 그 경로의 개수까지 구해야하는 문제다.

2. 풀이

경로를 큐에 넣고 하나씩 빼면서 확인을 하면된다.

다만 모든 경로를 큐에 집어넣게 되면 한번 움직일 때 마다 경로가 3배씩 늘어나 메모리 초과가 뜬다.
때문에 숨바꼭질 1처럼 경로가 중복되지 않게 큐에 넣는다.

횟수를 샐때 지금 이 경로가 가장 빠른 경로인지를 확인해줘야한다.
예를 들어 1에서 4까지 가는 경로라고 할 때 1-2-4 순으로 가는 경로가 가장 빠른 경로지만 1-2-3-4로 가는 경로도 있기 때문이다.

그래서 (1) 위치를 들렸는지 확인하는 변수를 선언하고 이 변수안에 해당 위치까지 가장 빠른 시간을 기록한다.
(가장 빠른 시간은 제일 먼저 큐에서 발견된 시간과 같다.)

(2) 경로의 가짓수를 기록하는 변수을 선언하여 경로의 개수를 구한다.

이미 들린 위치에 도착했으면 시간을 확인하여 가장 빠른 시간이면 횟수를 추가해주고, 아니면 그냥 넘어간다.

또한 같은 시간에 같은 위치를 들렸을 경우 그 위치 직전까지 모든 경로가 들릴 수 있는 경우가 되므로 +1 이 아닌 해당 경로까지 가짓수를 더 해준다.

3. 코드

#include <iostream>
#include <queue>
using namespace std;

int N, K;
int length[100001];	// (1) 이미 들린 위치인지 확인하는 변수
int visitCase[100001]; // (2) 해당 위치까지 도착하는 가장 빠른 경로들의 개수

int main()
{
	cin >> N >> K;
	
	queue<int> route;
	route.push(N);
	visitCase[N] = 1;
	
	while (!route.empty())
	{
		int cur = route.front();
		route.pop();

		int len = length[cur], cnt = visitCase[cur];

		if (cur == K)
			break;

		int nextPos = cur - 1;
		if (0 <= nextPos && nextPos <= 100000)
		{
			if (visitCase[nextPos] == 0)
			{
				route.push(nextPos);
				length[nextPos] = len + 1;
				visitCase[nextPos] = cnt;
			}
			else if (length[nextPos] == len+1)
			{
				visitCase[nextPos] += cnt;
			}
		}

		nextPos = cur + 1;
		if (0 <= nextPos && nextPos <= 100000)
		{
			if (visitCase[nextPos] == 0)
			{
				route.push(nextPos);
				length[nextPos] = len + 1;
				visitCase[nextPos] = cnt;
			}
			else if (length[nextPos] == len + 1)
			{
				visitCase[nextPos] += cnt;
			}
		}

		nextPos = cur * 2;
		if (0 <= nextPos && nextPos <= 100000)
		{
			if (visitCase[nextPos] == 0)
			{
				route.push(nextPos);
				length[nextPos] = len + 1;
				visitCase[nextPos] = cnt;
			}
			else if (length[nextPos] == len + 1)
			{
				visitCase[nextPos] += cnt;
			}
		}
	}

	cout << length[K] << "\n" << visitCase[K];
}

4. 후기

알고리즘 자체는 크게 어렵진 않았지만 메모리 초과를 어떻게 잡는지가 어려웠던 문제였다.

중복된 거리를 제거하는건 숨바꼭질 1과 같았지만 제거하면서 동시에 횟수를 체크해야되서 조금 복잡한것 같다.