[백준 13549 | C++] 숨박꼭질 3 :: 다익스트라

• 문제 링크 : 13549번: 숨바꼭질 3
• 관련 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 최단 경로, 데이크스트라, 0-1 너비 우선 탐색

 

풀이

이 문제가 다익스트라 태그인 것을 알았기 때문에 좀 더 쉽게 풀이를 떠올릴 수 있었습니다.

모델링이 어려운 문제였습니다. 다익스트라라면 그래프, 정점,간선와 가중치가 있어야 하는데 이 문제에서는 그래프가 명시적으로 보이지 않았기 때문에 낯설었습니다.

 

무엇을 정점/간선/가중치로 보아야 할까? 

정점과 정점사이는 간선을 따라 이동합니다. 즉, 간선은 정점 사이를 이동 가능하게 합니다

그렇다면 수빈이의 이동(걷기, 순간이동)을 간선으로 보면 어떨까? 수빈이의 이동가능한 경로를 간선으로 보면 어떨까?

 

그럼 이동에 걸리는 시간을 가중치로 보면 좋겠다는 생각이 듭니다...(마침 걷기와 순간이동에 걸리는 시간이 다르므로)

 

마지막으로 정점은 위치로 볼 수 있습니다. 이때 주의할 점은 n과 k사이의 모든 위치를 정점으로 두어야한다는 것입니다.  왜냐하면 위치가 5일때 걷는다면 4, 6으로 이동할 수 있기 때문에 필요합니다. 

 

모델링

코드

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

const int INF = 1 << 30;

using namespace std;

int n, k;

int dijkstra(int s, int e, vector < vector<pair<int, int>>>& g) {
	vector<int>dist(100000 + 1, INF);
	priority_queue<pair<int, int>>pq;

	dist[s] = 0;	// 시작점 0
	pq.push({ 0, s });

	while (!pq.empty()) {
		int cur_dist = -pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();

		if (cur_dist != dist[cur_node]) continue;

		for (auto x : g[cur_node]) {
			int nxt_dist = x.first + cur_dist;
			int nxt_node = x.second;

			if (nxt_dist < dist[nxt_node]) {
				dist[nxt_node] = nxt_dist;
				pq.push({ -nxt_dist, nxt_node });
			}
		}
	}

	return dist[e];
}

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

	cin >> n >> k;

	vector<vector<pair<int, int>>> g(100000 + 1);

	for (int i = 0; i <= 100000;i++) {
		if (i != 0) g[i].push_back({ 1, i - 1 });	// x - 1
		if (i != 100000) g[i].push_back({ 1, i + 1 });	// x + 1
		if (i * 2 <= 100000) g[i].push_back({ 0, 2 * i });	// 2 * x
	}

	cout << dijkstra(n, k, g);
}

 

• 문제의 제한 조건 : N(0 ≤ N ≤ 100,000), K(0 ≤ K ≤ 100,000)
• 최대 0 - 100,000의 정점을 만듭니다