[BOJ] 12851 : 숨바꼭질2 - travelbeeee

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

---

DP BFS

BFS 탐색에 DP를 적용해서 문제를 해결했습니다.

● DP[X] := start에서 시작해 X 지점에 오는데 필요한 최소 이동 횟수.

● 내가 현재 지점(x) 에서 점프 횟수가 y일 때, 다음에 이동할 지점의 DP 값이 y + 1 보다 작으면 최소 이동 횟수가 아니므로 점프를 하지 않고, 또 y + 1이 현재 정답(end에 오는데 필요한 최소 점프 횟수) 보다 크면 최소 이동 횟수가 아니므로 점프를 하지 않아도 됩니다.

#include<iostream>
#include<queue>
#define INF 99999999
using namespace std;

int dp[200001] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, K, ans = INF, cnt = 0;
	cin >> N >> K;

	queue<pair<int, int>> q;
	q.push({ N, 0 });
	for (int i = 0; i < 200001; i++)
		dp[i] = INF;

	while (!q.empty()) {
		pair<int, int> cur = q.front(); 
		q.pop();
		if (cur.first == K) {
			ans = min(ans, cur.second);
			if (ans == cur.second)
				cnt++;
		}
		if (0 <= cur.first - 1 && cur.second + 1 <= dp[cur.first - 1] && cur.second + 1 <= ans){
			dp[cur.first - 1] = cur.second + 1;
			q.push({ cur.first - 1, cur.second + 1 });
		}
		if (cur.first + 1 <= K && cur.second + 1 <= dp[cur.first + 1] && cur.second + 1 <= ans){
			dp[cur.first + 1] = cur.second + 1;
			q.push({ cur.first + 1, cur.second + 1 });
		}
		if (cur.first * 2 <= 200000 && cur.second + 1 <= dp[cur.first * 2] && cur.second + 1 <= ans){
			dp[cur.first * 2] = cur.second + 1;
			q.push({ cur.first * 2, cur.second + 1 });
		}
	}
	cout << ans << '\n' << cnt;
	return 0;
}

---