백준 Gold 4 숨바꼭질 4

숨바꼭질 4 (백준 Gold 4)

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

이전에 풀었던 숨바꼭질 2와 유사하나
n,k가 주어졌을때, 다음의 계산을 통하여
n이 k가 되는 최소 시간과 그 경로를 구하는 문제

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

다만,
경로는 다양한 경우의 수가 나올 수 있으니
그 중 하나를 제출하여도 정답으로 침

풀이 방법

이전에 푼 방식대로 N->K가 아닌
K->N의 방식으로 진행

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

Visit 용 Unordered_map 뿐 아니라
‘경로’ 표기용으로
routes 라는 해시 맵도 사용하였다

• 이전에 방문한 위치를 저장해두어야 하기에
  infos라는 구조체를 통해 BFS 탐색 진행
  

• 이전에 ‘밟’은 곳이라면 사실상 재 방문할 수 없기에
  (더 빨리 밟았다면 다른 쪽에서 못 밟으므로)
  routes[현재 위치] = 이전 위치를 통해
  대략적인 경로를 저장해놓는다
  

• 탐색이 끝난 후
  start = n , target = k 로 잡은 후
  routes를 거슬러 올라가며 출력하면
  경로를 출력할 수 있다
  

제출 코드

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

using namespace std;

struct infos
{
	int now, prev;
	int nowCost;
};

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

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

	int bestTime = -1;
	int bestCount = 0;

	q.push({ k,0 });
	routes[k] = k;

	while (q.empty() == false)
	{
		int nowPos = q.front().now;
		int nowTime = q.front().nowCost;
		int prev = q.front().prev;
		q.pop();

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

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

		visit[nowPos] = nowTime;
		routes[nowPos] = prev;

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

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

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

	cout << bestTime << '\n';

	int start = n;
	int target = k;

	while (start != target)
	{
		cout << start << " ";
		start = routes[start];
	}

	cout << k;

	return 0;
}

결과

이전에 한 번 푼 문제이기도 하고
‘경로’를 어떻게 저장할지를 잘 고민하여 풀 수 있는 문제였다

• 만약 Vector 로 저장하였다면 Queue로 인하여 메모리가 터질 가능성 존재
  

• 이미 최단 경로를 검사하고 있으니 사실상 다른 노드가 ‘해당 노드를 밟아’
  map을 어지럽힐 가능성이 없다 생각하여 위와 같이 풀 수 있었다