boj, 백준) 11779. 최소비용 구하기2 (C/C++)

1. 문제 링크

www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

 

2. 문제 개요

간선이 주어지고 출발지, 도착지의 정점 번호가 주어질 때, 출발지, 도착지까지의 최단거리, 경로를 구하는 프로그램을 작성하시오.

 

3. 문제 힌트

(1) 인접 리스트로 나타낼 것. -> 한 정점에서 다른 정점까지의 간선이 1개라면 행렬로 나타내어도 괜찮다. 그런데 한 정점에서 다른 정점까지 간선이 여러 개 있을 수 있으니 인접 리스트로 나타내어야 한다.

 

그 외 특별히 주의할 점은 없다. 

n이 최대 1000이라 O(n^2) dijkstra알고리즘을 써도 될 것 같지만 이왕 문제 푸는 거 우선순위 큐를 사용해보자.

 

4. 문제 풀이

맞은사람이 많아서 풀이를 안 하려고 했다. 다른 더 똑똑하신 분들이 이미 잘 써놓으셨을 거라고 생각했기 때문. 그런데 문제가 너무 전형적이고, formal 하다고 해야 할까..  꼭 알아야만 할 것 같아서 복습, 메모도 할 겸.. 업로드를 합니다.

 

풀이라고 해야 할까, 특별한 트릭이 없다.

최단 거리를 못 찾는 것은 인접 행렬에서 우선순위 큐로 자료구조를 변경했을 때 아직 알고리즘 내부에서 어떤 부분이 어떻게 바뀌었는지를 이해하지 못하기 때문이라고 생각한다. 

 

최단 경로를 못 찾는 이유는 dijkstra알고리즘 그 자체의 원리를 한번 더 공부할 필요가 있다고 생각한다. 언제 값이 갱신되고, 갱신할 때 어떤 값을 어떻게 저장하면 경로를 저장할 수 있는지...

 

(원리에 대해서는 다른 블로그에 더 훌륭하신 분들이 정리하신 내용이 이미 많으니 생략하겠습니다.^_^)

 

간단히..

인접 행렬이랑 우선순위 큐의 차이점은 이때까지 최단경로를 찾은 정점들의 집합에 연결된 모든 정점들에 대해서 어떻게 최솟값을 찾을 건지에 달려있습니다.

인접 행렬 같은 경우는 O(n), 즉 처음부터 끝까지 순회하면서 최솟값을 찾고, 우선순위 큐는 힙 정렬을 통해 O(logn)만에 최솟값을 찾습니다.

 

우선순위 큐에는 최단경로일 것 같은 후보 정점들을 큐에 넣어 최솟값을 구하기 때문에 조건에 만족하지 않는 후보들을 제거하기 위해 while문의 시작 부분에 continue부분이 있어야 합니다.

 

5. 코드

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

struct ITEM {
	ITEM() {}
	ITEM(int dist_, int cur_) :dist(dist_),cur(cur_){}
	int dist, cur;

	bool operator<( const ITEM &other)const {
		return this->dist < other.dist;
	}
};

const int INF = 987654321;
int n, m;
vector<vector<pair<int, int>>> adj;	//next, weight
vector<int> parent,dist, path;

priority_queue<ITEM> pq;
int dep, ari; //departure, arrival

int main()
{
	scanf("%d", &n);
	scanf("%d", &m);
	adj.resize(n + 1);	//for [0,n]
	parent.resize(n + 1);
	dist.resize(n + 1, INF);	// I dont have any information about shortest distance -> INF

	for (int i = 0; i < m; ++i) 
	{
		int from, to, weight;
		scanf("%d %d %d", &from, &to, &weight);

		adj[from].push_back({ to,weight });
	}

	scanf("%d %d", &dep, &ari);
	dist[dep] = 0;

	pq.push(ITEM(dist[dep],dep));

	while (!pq.empty()) 
	{
		ITEM item = pq.top(); 
		pq.pop();

		if (dist[item.cur] < item.dist)	
			continue;	//remove unnecessary candidates

		//compare all vertices that are connected to item.cur to get the shorest path
		for (pair<int, int> e : adj[item.cur])
		{
			int next = e.first;
			int weight = e.second;

			if (dist[next] > dist[item.cur] + weight) {
				dist[next] = dist[item.cur] + weight; //update
				parent[next] = item.cur;	//for path....tracing
				pq.push(ITEM(dist[next], next));	// next vertex is a candidate so far of shortest path, 
			}
		}
	}

	for (int v = ari; v != 0; v = parent[v]) 
		path.push_back(v);	//it acts like the 'stack'

	printf("%d\n%d\n",dist[ari], path.size());
	
	for (int i = path.size() - 1; i >= 0; --i)
		printf("%d ", path[i]);

	return 0;
}

 

6. 결과