[BOJ] 12851 숨바꼭질 2

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

12851번: 숨바꼭질 2

 

알고리즘: DP, BFS

 

시간복잡도: O(V+E)

---

BOJ 1697 숨바꼭질의 업그레이드 버전이다.

https://moon323.tistory.com/16

 

N에서 K까지 이동하는데 걸리는 최단 시간뿐만 아니라 그 방법의 가짓수도 구해야한다.

 

접근:

1. 가짓수 구하기

 

-> 가짓수 구하는 문제이므로 Dynamic을 이용하면 된다.

 

 

D[i]: i 좌표까지 가는 방법의 가짓수 로 두고

queue에 이동할 좌표들을 넣을 때, DP 배열도 같이 갱신해주면 된다.

 

D[X*2] = D[X*2]+D[X]

D[X-1] = D[X-1]+D[X]

D[X+1] = D[X+1]+D[X]  이런 식으로..

 

 

주의)

이 문제는 도중에 좌표가 10^5을 넘기는 경우도 고려해줘야 한다.

// Dp 로 접근해야함. ㅎ;

#include <iostream>
#include <queue>
using namespace std;
int N, K, D[100001*2], h, c[100001*2];
queue <int> Q;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> K;
	
	Q.push(N);
	D[N] = 1;
	c[N] = 1;
	while (!Q.empty())
	{
		h = Q.front();
		if (h == K) break;
		if (h-1 >= 0)
		{
			if (!c[h-1])
			{
				c[h-1] = c[h] + 1;
				Q.push(h-1);
			}
			if (c[h-1] == c[h]+1)
				D[h-1] += D[h];
		}
		if (h < K)
		{
			if (!c[h+1])
			{
				c[h+1] = c[h] + 1;
				Q.push(h+1);
			}
			if (!c[h*2])
			{
				c[h*2] = c[h] + 1;
				Q.push(h*2);
			}
			if (c[h+1] == c[h]+1)
				D[h+1] += D[h];
			if (c[h*2] == c[h]+1)
				D[h*2] += D[h];
		}
		Q.pop();
	}
	cout << c[K]-1 << "\n" << D[K];
	return 0;
}