#12851. 숨바꼭질 2

Problem

• 문제링크

Solution

• 방법의 수를 구하는 것이 추가가 되었다.
• 이는 DP를 활용하여 구한다.
• 방문하지 않은 경로라면 방법의 수는 그대로 유지
• 방문한 경우 + 거리 차이가 1인 경우에만 방법의 수+1
  거리 차이가 1인 경우에만 최소비용을 만족하는 경로이기 때문이다.

1 Try

#include <iostream>
#include <queue>
#define MAX 100000
using namespace std;
int N, K;
queue<int> q;
bool visit[MAX+1];
int dist[MAX + 1];
int cnt[MAX + 1];
void BFS() {
	q.push(N);
	visit[N] = true;
	dist[N] = 0;
	cnt[N] = 1;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int next : {x - 1, x + 1, x * 2}) {
			if (0 <= next && next <= MAX) {
				if (!visit[next]) {
					visit[next] = true;
					dist[next] = dist[x] + 1;
					cnt[next] = cnt[x];
					q.push(next);
				}
				else if (dist[next] == dist[x] + 1) {
					cnt[next] += cnt[x];
				}
			}
		}
		
	}
}
int main() {
	cin >> N >> K;
	BFS();
	cout << dist[K] << "\n" << cnt[K] << "\n";
	return 0;
}