백준 - 숨바꼭질 3 (13549) [C++]

이 문제는 다익스트라를 이용해서 풀었다.

 

이 문제에서 핵심은 +1, -1, *2를 수행할 때 현재와 목적지와의 관계를 비교하지 않는 것이다.

이는 예제에서 말해주고 있다. 출발지가 5이고, 도착지가 17인데, 10에서 9로 가는 선택이 들어간다.

 

내가 했던 실수는 여기서 현재가 도착지보다 작을 경우, 0이 아니면 *2, +1 을 수행하고, 0이면 +1을 수행하는 식의 로직이 추가되었다는 점이다. 이러면 10에서 9로 가는 로직이 형성되지 않는다.

 

현재와 목적지까지의 상대 위치를 판단하지 않으면 큐에 너무 많은 숫자가 들어오게 되는데, 이를 방지하기 위해 다익스트라 알고리즘을 사용할 수 있다. 다익스트라를 이용하면 항상 현재 비용이 가장 적은 것부터 수행하기 때문에, 정답에 도착했을 때 바로 리턴해도 그것이 정답임을 확신할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <utility>
using namespace std;

#define MAX 300000
#define INF 1000000000

int N, K;

struct Compare {
	bool operator() (pair<int, int> &a, pair<int, int> &b) {
		return a.second > b.second;
	}
};

bool inRange(int x) {
	if (0 <= x && x <= MAX) {
		return true;
	}
	return false;
}

int dijkstra(int start, int end) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> q;
	vector<int> dist(MAX + 1, INF);
	q.push({ start , 0});
	dist[start] = 0;

	while (!q.empty()) {
		int present = q.top().first;
		int presentCost = q.top().second;
		q.pop();

		if (present == end) {
			return presentCost;
		}

		// * 2
		if (inRange(present * 2) && present != 0) {
			int next = present * 2;
			int nextCost = presentCost;

			if (dist[next] > nextCost) {
				dist[next] = nextCost;
				q.push({ next, nextCost });
			}
		}

		// -1
		if (inRange(present - 1)) {
			int next = present - 1;
			int nextCost = presentCost + 1;

			if (dist[next] > nextCost) {
				dist[next] = nextCost;
				q.push({ next, nextCost });
			}
		}

		// + 1
		if (inRange(present + 1)) {
			int next = present + 1;
			int nextCost = presentCost + 1;

			if (dist[next] > nextCost) {
				dist[next] = nextCost;
				q.push({ next, nextCost });
			}
		}
	}

	return -1;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> K;
	int answer = dijkstra(N, K);
	cout << answer << '\n';

	return 0;
}