[백준] 1753 최단경로 - C++

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

---

본격적으로 다익스트라 알고리즘을 배우기 위해 풀어보았다.

 가중치가 있는 그래프에서의 최단경로를 구해야 하기 때문에 다익스트라 알고리즘을 사용했다.

---

부분 코드 설명

//전역
const int INF = 1e9;
int V, E, K;

다익스트라 알고리즘에 필요한 무한을 대표할 값을 정해준다. 넉넉하게 10억으로 해준다.

문제에서 주어지는 V, E, K 변수를 선언해준다.

 

//전역
vector<pair<int, int> > graph[20'001];
vector<int> dist;

그래프를 인접리스트로 표현하기 위해

pair형 vector형 배열을 선언해준다. (와우..)

graph[1] = { {2, 3}, {4, 7} }

라면, 1번 노드에서

---  2번 노드로 향하는 가중치 3의 링크

---  3번 노드로 향하는 가중치 7의 링크

를 나타낸다.

시작 노드부터 인덱스번째 노드까지의 최단거리를 저장하기 위해 dist vector를 선언한다.

 

daik 함수 내부 설명

dist.assign(V + 1, INF);

dist(최단거리 저장)의 V+1개의 값을 무한으로 저장해준다.

priority_queue<pair<int, int>, vector <pair<int,int> > , greater<> > pq;

다익스트라의 핵심인 우선순위큐를 선언해준다.

자료형은 거리, 노드번호를 저장하는 pair형으로 선언한다,

컨테이너는 자료형에 맞춰 pair형 vector로 선언했고, 거리가 가까운 노드부터 탐색하기 때문에 greater로 정렬한다.

dist[start] = 0;
pq.push({ 0, start });

시작 노드에서 시작 노드까지의 거리는 당연히 0이다.
큐에 시작 노드를 넣어준다.

 

while (!pq.empty()) {
	auto [cur_dist, cur] = pq.top(); //<1>
	pq.pop();
	if (dist[cur] < cur_dist) { //<2>
		continue;
	}
	for (auto [next, cost] : graph[cur]) { //<3>
		if (dist[next] > cur_dist + cost) { //<4>
			dist[next] = cur_dist + cost;
			pq.push({ dist[next], next });
		}
	}
}

큐가 빌 때까지 이하의 코드를 반복할 것이다.

<1> : 큐의 값(pair형)을 빼와 first는 cur_dist에, second는 cur에 저장한다.

저 수상한 auto와 대괄호는 C++17에 도입된 기능인 구조적 바인딩이다. 아무튼 저걸 이용해 pair의 값을 따로따로 저장해준다.

<2> : 이전에 계산해 둔 최단 거리가 큐에서 꺼낸 값보다 작다면, 그냥 원래 있던게 최단거리이기 때문에 continue한다.

<3> : 또 수상한 auto와 대괄호이다.. graph[cur]에 저장된(=현재 노드와 연결된)노드를 하나씩 뽑아가며 for문을 돌리겠단 뜻이다.

<4> : <3>에서 뽑은 (다음 노드의 기존 최단거리)가 (현재 노드까지의 최단거리 + 다음 노드까지의 가중치)보다 크다면, 최단거리는

(현재 노드까지의 최단거리 + 다음 노드까지의 가중치)이기 때문에 (다음 노드의 기존 최단거리)를 해당 값으로 정하고, 큐에 push한다.

 

메인 함수 설명

int main() {
	cin >> V >> E >> K;
	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		graph[u].push_back({v, w});
	}
	daik(K);
	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF) {
			cout << "INF\n";
		}
		else {
			cout << dist[i] << "\n";
		}
	}
	return 0;
}

V, E, K를 입력받고, 링크의 정보를 저장한다. (방향그래프이다!)

daik함수를 호출해 연산을 수행한다.

for문을 돌리며 dist에 저장된 최단거리를 출력한다.

경로가 존재하지 않는 경우(=dist가 초깃값인 INF 그대로인 경우)에는 INF를 출력해준다.

 

전체 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9;
int V, E, K;
vector<pair<int, int> > graph[20'001];
vector<int> dist;
void daik(int start) {
	dist.assign(V + 1, INF);
	priority_queue<pair<int, int>, vector <pair<int,int> > , greater<> > pq;
	dist[start] = 0;
	pq.push({ 0, start });
	while (!pq.empty()) {
		auto [cur_dist, cur] = pq.top();
		pq.pop();
		if (dist[cur] < cur_dist) {
			continue;
		}
		for (auto [next, cost] : graph[cur]) {
			if (dist[next] > cur_dist + cost) {
				dist[next] = cur_dist + cost;
				pq.push({ dist[next], next });
			}
		}
	}
}
int main() {
	cin >> V >> E >> K;
	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		graph[u].push_back({v, w});
	}
	daik(K);
	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF) {
			cout << "INF\n";
		}
		else {
			cout << dist[i] << "\n";
		}
	}
	return 0;
}

---

어렵다 어려워..

다른 다익스트라 문제도 풀어보며 더 연습하도록 하자!

---