(백준) 1162번 - 도로 포장

문제

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

풀이

기존 다익스트라 방식에서, dist 배열에서 포장한 도로 정보까지 관리해야 한다. 이차원 dist 배열을 선언하고, dist[i][j] 를 출발지에서 i번 째 도로까지 j개의 도로를 포장한 경우의 최소 비용을 저장하면 된다.

코드

#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>

#define INF 1e12

using namespace std;

vector<pair<int, int>> graph[10001];
long long dist[10001][21]; // dist[i][j]: 출발지부터 i까지 j개의 도로를 포장한 경우 최소 비용

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		graph[a].push_back({ b,c });
		graph[b].push_back({ a,c });
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= k; j++) {
			dist[i][j] = INF;
		}
	}

	priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> pq; // 가중치, 노드, 포장한 도로 수
	pq.push({ 0,1,0 });
	dist[1][0] = 0;

	while (!pq.empty()) {
		long long w = get<0>(pq.top());
		int node = get<1>(pq.top());
		int cnt = get<2>(pq.top());
		pq.pop();

		if (dist[node][cnt] < w) continue;

		for (int i = 0; i < graph[node].size(); i++) {
			int nnode = graph[node][i].first;
			int nw = graph[node][i].second;

			// 도로를 포장할 수 있다면
			if (cnt < k && dist[nnode][cnt + 1] > w) {
				dist[nnode][cnt + 1] = w;
				pq.push({ dist[nnode][cnt + 1],nnode,cnt + 1 });
			}

			// 그냥 가는 경우
			if (dist[nnode][cnt] > w + nw) {
				dist[nnode][cnt] = w + nw;
				pq.push({ dist[nnode][cnt],nnode,cnt });
			}
		}
	}

	long long ans = INF;
	for (int i = 0; i <= k; i++) {
		ans = min(ans, dist[n][i]);
	}
	cout << ans;
}

시간복잡도

일반적으로 다익스트라 알고리즘의 시간복잡도는 $O(ElogV)$이다. 다만 이 문제는 단순히 $N$개의 도시만 있는 것이 아니라, 각 도시마다 포장 횟수라는 상태가 존재하므로, 실제 노드의 수는 $N \cdot K$라고 할 수 있다. 마찬가지로 간선 또한 포장하고 이동, 포장하지 않고 이동이라는 상태가 존재하므로, 총 간선의 수는 $M \cdot K$라고 할 수 있다. 따라서 전체 시간복잡도는 $O(K \cdot Mlog(N \cdot K))$라고 할 수 있다.

공간복잡도

graph 에서 공간복잡도는 $O(N+M)$, dist 배열에서 $O(N \cdot K)$, 우선순위 큐에서 최악의 경우 모든 간선의 정보가 삽입될 수 있으므로 $O(M \cdot K)$이다. 따라서 전체 공간복잡도는 $O((N+M)\cdot K)$이다.