[BOJ] 1162:도로포장

 

 

0. 문제

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

1162번: 도로포장

 

1. 문제 분석

- 이 문제는 양방향 그래프에서 정해진 정점(1번 도시, 서울)을 기준으로 다른 정점(N번 도시, 포천)까지의 최단 거리를 계산하는 문제이다. 따라서 단일 출발점 최단경로 문제(Single Source Shortest Problem)의 풀이 방법인 다익스트라 알고리즘(Dijkstra Algorithm) 또는 벨만-포드 알고리즘(Bellman-Ford Algorithm)을 사용할 수 있다. 

- 설명에서는 누락되었지만, 이 문제에서는 '이미 존재하는' 서로 다른 두 도시 간의 도로들 중 K개 이하의 임의의 도로를 포장해야 한다. 따라서 도로가 포장되는 여러 경우에 따른 최단거리를 메모이제이션 해주는 동적계획법(dynamic programming)을 사용해야 한다. 

 

2. 유의할 점

- 이 문제의 경우, 경로들의 비용(통과하는데 걸리는 시간)은 음수가 아니기 때문에 음의 사이클 발생 가능성이 없으므로, 시간복잡도가 비교적 작은 다익스트라 알고리즘을 사용했다.

- 다익스트라 알고리즘의 경우, 우선순위 큐를 사용해야 하므로, 우선순위 큐의 자료형으로 사용할 간선(edge)을 구조체로 선언하고, 구조체 선언 시 비교 연산자(<)에 대해 오버로딩 해주어야 한다. 또한 얼마 만큼의 도로를 더 포장할 수 있는지, 그 남은 횟수에 대한 정보도 같이 담겨야 하므로 이와 관련한 멤버 변수(아래 코드에서는 left) 역시 설정해주어야 한다.

- 얼마만큼의 도로를 더 포장할 수 있는지를 알 수 있는 각각의 경우에서 해당 도시까지의 최단 거리에 대해 계산해주어야 하므로, 2차원 배열로 최단 거리를 메모이제이션 해주는 동적 계획법(dynamic programming)이 필요하다. 이를 위해 각 경우의 최단거리에 대한 정보를 저장할 수 있는 dist[i][j](j개의 도로를 더 포장할 수 있을 때, i번 도시까지의 최단거리)의 배열을 선언했다.

 

2-1. 다익스트라 알고리즘(Dijkstra Algorithm)

- 다익스트라 알고리즘은 하나의 정점을 기준으로 다른 정점까지의 거리를 계산하는 알고리즘이다. 기본적으로는 방향그래프에 대해서 사용한다. 여기서 말하는 최단거리는 몇 개의 간선을 지났는지를 세는 것이 아니라, 각 간선에 부여된 가중치의 합을 최소화 한 것 말한다.

- BFS와 같이, 시작 정점에서 출발해 연결되어 있는 정점들로 뻗어 나가면서 시작 정점부터 해당 정점까지의 거리를 갱신하는 것이다. 이를 위해 처음에는 모든 정점까지의 거리를 INF(어떤 정점까지의 거리보다도 큰 수)로 초기화 해주고, 시작 정점까지의 거리는 0으로 초기화 해주어야 한다.

//0번 정점에서 다른 정점까지의 최단거리를 저장하는 배열
int dist[N];

// 초기화
for (int i = 0; i < N; i++) dist[i] = INF;
dist[0] = 0;

 

- 최단거리를 갱신하는데 있어서 가장 기본이 되는 개념은, 코드가 진행되면서 여태까지 구했던 시작 정점 s부터 임의의 정점 v까지의 최단거리인 dist[v](소스 코드가 더 진행되면서 갱신될 여지가 있는 거리)는 정점 s부터 임의의 정점 u까지의 최단거리와 u부터 v까지의 거리(u와 v를 잇는 간선의 가중치)를 합한 것보다 크거나 같다는 것이다.

dist[v] <= dist[u] + weight(u, v)

 

- 다익스트라 알고리즘을 구현한 가장 기본적인 형태는 해당 지점까지의 거리와 해당 지점의 정보를 담는 pair를 자료형으로 갖는 우선순위 큐를 사용하여, 큐 안의 가장 짧은 거리를 갖는 pair형 인스턴스부터 꺼내, 이를 갱신하는 것이다. 이 때, 우선순위 큐는 가장 큰 값부터 pop 할 수 있도록 설계되어 있으므로, 거리는 음수로 표현하여 큐 안에 넣는다. 이를 통해 거리를 오름차순으로 큐 내에서 뽑아낼 수 있다.

int v, e, k;
int uu, vv, ww;
priority_queue<pair<int, int>> pq;

// first: weight & second: to
vector<pair<int,int>> gph[20001];
cin >> v >> e >> k;

// 초기화
vector<int> dist(v + 1, INF);
dist[k] = 0;
pq.push({ 0, k });

// 간선의 시작점과 끝점, 가중치를 입력받아 방향그래프 정보 저장
while (e--) {
   	cin >> uu >> vv >> ww;
	gph[uu].push_back({ ww, vv });
}

while (!pq.empty()) {
   	// 가장 값이 작은 간선을 뽑기 위해 음수화
	int cost = -pq.top().first;
	int here = pq.top().second;
	pq.pop();
    
    // 큐에 들어간 해당 정점까지의 거리가 더 커서 갱신이 불가능 하다면 무시
	if (dist[here] < cost) continue;
	for (int i = 0; i < gph[here].size(); i++) {
		int there = gph[here][i].second;
		int to_there = cost + gph[here][i].first;
        
        // 거리를 갱신할 수 있다면 갱신하고 큐에 넣어서 BFS 진행
		if (dist[there] > to_there) {
			dist[there] = to_there;
			pq.push({ -to_there, there });
		}
	}
}

 

3. 소스 코드(C++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <tuple>
#define endl '\n'
#define INF 50000000001
using namespace std;
typedef long long ll;

typedef struct edge {
	ll cost;
	int to, left;
	bool operator <(edge ee) const{
		return cost < ee.cost;
	}
}edge;

int n, m, k;
vector<edge> gph[10001];
priority_queue<edge> pq;
ll dist[10001][21];

void dijkstra() {
	while (!pq.empty()) {
		ll to_here = -pq.top().cost;
		int here = pq.top().to;
		int builtable = pq.top().left;
		pq.pop();

		if (to_here > dist[here][builtable]) continue;

		for (int i = 0; i < gph[here].size(); i++) {
			int there = gph[here][i].to;
			ll to_there = gph[here][i].cost + to_here;
			if (builtable > 0 && 
				dist[there][builtable - 1] > to_here) {
				dist[there][builtable - 1] = to_here;
				pq.push({ -to_here, there, builtable - 1 });
			}
			if (dist[there][builtable] > to_there) {
				dist[there][builtable] = to_there;
				pq.push({ -to_there, there, builtable});
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int fr, to, wt;
	ll ans = INF * 10;
	cin >> n >> m >> k;
	while (m--) {
		cin >> fr >> to >> wt;
		gph[fr].push_back({ wt, to, k });
		gph[to].push_back({ wt, fr, k });
	}

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

	dijkstra();
	for (int i = 0; i <= k; i++)
		ans = min(ans, dist[n][i]);
	cout << ans;

	return 0;
}

 

4. 여담

- 다익스트라와 dp 개념이 결합된 어려운 문제였다.. 애증의 dp...

- 의외로 INF값 때문에 문제가 생겨서 애를 먹었다. INF값을 아무 생각없이 기존처럼 987654321 define 했다가 문제의 엄청난 간선 수와 최대 가중치 간의 콜라보레이션으로 인해 훨씬 더 큰 INF 값이 필요했던 것이다.....