백준 Gold 4 숨바꼭질 2

숨바꼭질 2 (백준 Gold 4)

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

n,k가 주어졌을때, 다음의 계산을 통하여
n이 k가 되는 최소 시간과 그 경우의 수를 구하는 문제

• n * 2
  
• n + 1
  
• n - 1
  

풀이 방법

일반적인 BFS를 통해
Queue를 이용하여 구할 수 있는 문제이다

현재 값에 위의 수식들을 적용하면 풀 수 있으나…
메모리 초과가 발생하기 쉽다

따라서 계산을 ‘역’으로 해야 문제를 해결할 수 있다!

k -> n
그렇기에 수식도 변화한다

• k / 2 (단, 2로 나뉘는 경우)
  
• k - 1
  
• k + 1
  

해당 조건으로 풀면 queue에 너무 많은 가짓수가 들어가지 않기에
메모리 초과를 피할 수 있다

• 또한 중복 방문을 피하기 위하여
  unordered<int,int>를 통해
  방문 위치 , 최소 시간 을 통하여
  가짓수를 더욱 줄였다
  

제출 코드

#include<iostream>
#include<queue>
#include<unordered_map>

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;

	// 현재 위치, 시간
	queue<pair<int, int>> q;
	unordered_map<int, int> visit;

	int bestTime = -1;
	int bestCount = 0;

	q.push({ k,0 });

	while (q.empty() == false)
	{
		int nowPos = q.front().first;
		int nowTime = q.front().second;
		q.pop();

		if (bestTime != -1 &&
			nowTime > bestTime)
			break;

		if (visit.find(nowPos) != visit.end() &&
			visit[nowPos] < nowTime)
			continue;

		visit[nowPos] = nowTime;

		if (nowPos == n)
		{
			if (bestTime == -1 ||
				nowTime == bestTime)
			{
				bestTime = nowTime;
				bestCount++;
				continue;
			}
		}

		if (nowPos % 2 == 0)
			q.push({ nowPos / 2,nowTime + 1 });

		q.push({ nowPos - 1,nowTime + 1 });
		q.push({ nowPos + 1,nowTime + 1 });
	}

	cout << bestTime << '\n';
	cout << bestCount << '\n';

	return 0;
}

결과

n이 k가 되는 것은 무수히 많은 계산을 낳을 수 있으나
k에서 n으로 가는 것이 더 경우의 수가 작을 수 있다는 것을 다시 한번 느꼈다
(n*2 보다는 k / 2(2로 나뉜다면) 쪽이 가짓수가 줄어듦)

마지막에 틀린건 혹시 첫 코드로 다시 시도해본 것!