백준 - 12851 숨바꼭질2

문제

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

12851번: 숨바꼭질 2

수빈이가 움직일 수 있는 방법은 3가지이고 동생이 있는 위치까지 갈 수 있는 가장 빠른 시간과 그 시간으로 찾는 방법의 개수를 구하는 문제였다.

 

수빈이는 1초 후에 다음과 같이 이동할 수 있다.

X-1
X+1
X*2

 

문제 풀이

처음에는 DP만을 가지고 이 문제를 풀려고 했는데, 방법의 개수를 구하는 것이 너무 어려웠다.. 직전에 갱신한 방법이 무엇인지도 써줘야 하나 하고 고민하다가 문제 유형을 확인했는데 그래프..! BFS..! 였다,, 마음을 가다듬고 해당 방법으로 다시 풀었다.

 

먼저 현재 위치에서 갈 수 있는 다음 목적지 3곳을 탐색해야 한다. 이때 dp 배열에 저장되어 있는 최소 시간보다 작거나 같을 때에만 queue에 넣어줬다. 방법의 개수를 구하기 위해 같을 때에도 넣어줬다.

 

계속해서 queue를 pop하고 push를 반복해주면서 현재 노드가 K와 같을 때 queue에서 해당 시간인 것까지 모두 pop 해주면서 다른 방법이 있는지 찾은 후 최소 시간과 방법의 개수를 반환했다.

 

bfs와 dp를 같이 사용한 적은 이번이 처음인데 다음부터 이런 문제가 나온다면 이번보다는 쉽게 풀 수 있을 것 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int N, K;
int dp[200001];
int nx[3] = { 1,-1,2 };

pair<int, int> findMinTime() {
	priority_queue<pair<int,int>> pq; //time, node
	int minTime, cnt;
	minTime = -1;
	cnt = 0;
	dp[N] = 0;

	pq.push({ 0,N });

	while (!pq.empty()) {
		int nowTime = -pq.top().first;
		int nowNode = pq.top().second;
		pq.pop();
		//printf("nowNode: %d time: %d\n", nowNode, nowTime);
		if (nowNode == K) {
			minTime = nowTime;
			cnt = 1;
			while (!pq.empty()) {				
				//printf("nowNode: %d time: %d\n", pq.top().second, -pq.top().first);
				if (-pq.top().first == nowTime) {
					if (pq.top().second == nowNode) {
						cnt++;						
					}
				}
				else {
					break;
				}
				pq.pop();
			}
			return { minTime, cnt };
		}
		//dp보다 작거나 같을때만 push
		for (int i = 0; i < 3; i++) {
			int nextNode;
			if (nx[i] == 2) {
				nextNode = nowNode * 2;
			}
			else {
				nextNode = nowNode + nx[i];
			}
			if (nextNode > 200000) continue;
			if (dp[nextNode] >= dp[nowNode] + 1) {				
				dp[nextNode] = dp[nowNode] + 1;				
				pq.push({ -(nowTime + 1), nextNode });
			}			
		}
	}
	
	return { minTime, cnt };
}

int main(int argc, char** argv)
{
	scanf("%d %d", &N, &K);

	fill(&dp[0], &dp[200000], 100001);

	pair<int,int> answer = findMinTime();

	printf("%d\n%d", answer.first, answer.second);

	return 0;
}