이코테 최단경로 : 전보 [C++] - 다익스트라

 

 

알고리즘을 풀기 전,

최단 경로 알고리즘은 크게 두가지로 나뉜다는 것을 배웠다.

다익스트라 알고리즘은 그리디 알고리즘의 성격을 띠며 한지점에서 여러지점으로 가는 최단 경로를 구한다.

플루이드 워셜 알고리즘은 여러지점에서 여러지점으로 가는 최단 경로를 구한다.

 

따라서, 다익스트라는 배열에 노드별 결과값을 저장하며 플루이드 워셜은 이차원 배열에 결과값을 저장한다.

 

---

 

이번에 풀어본 "전보"라는 문제는 시작지점인 START에서 다른 노드들로 가는 최단 거리를 구한 다음, 

도달할 수 있는 노드의 갯수와 구한 최단 거리들 중 가장 짧은 거리를 구하는 문제였다.

 

 

문제는 다음과 같다. 

 

 

풀이는 다음과 같다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#define INF 1e9

using namespace std;

// 노드의 개수(N), 간선의 개수(M), 시작노드 번호(Start)
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int>> graph[30001];
// 최단 거리 테이블 만들기 - 시작노드인 start에서 가는 모든 노드들의 거리 저장
int d[30001];

void dijkstra(int start) {
	// 가장 짧은 거리의 간선이 top에오는 pq
	priority_queue<pair<int, int>> pq;
	
	// 시작노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
	pq.push({ 0, start });
	// 시작노드인 자기자신으로 가는거리는 0으로 세팅
	d[start] = 0;

	while (!pq.empty()) {	// 큐가 비어있지 않다면
		// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
		int dist = -pq.top().first;	// 현재 노드까지의 비용
		int now = pq.top().second;	// 현재 노드
		pq.pop();

		// 현재 노드가 이미 처리된 적이 있는 노드라면 무시 
		// **** 해당 알고리즘인 다익스틀라 알고리즘은 그리디 알고리즘적이라는 것을 명심해야함
		// **** 만약 현재 선택된 간선이 현재 노드까지 오는 최단 거리라면..
		// **** 현재 간선의 길이와 현재 노드와 연결된 다른 노드들을 아래의 for문을 통해서 pq에 넣어야한다.
		// **** 그렇게 연결된 다른 노드들까지의 최단 거리도 구하게 되는 것.
		// d[now]와 dist를 비교했을 때 나올수있는 경우의 수는 두가지다.
		// 1) d[now] == dist : 현재 간선이 now까지의 최단거리일 경우
		// 2) d[now] < dist  : 이미 전에 now까지의 최단거리 간선을 발견해서 그 간선으로 아래의 for문이 실행된 경우
		// 따라서 아래 if문의 경우 이미 최단 거리 간선이 발견된 이후이기 때문에 아래 for문을 건너뛴다.
		if (d[now] < dist) continue;

		// 현재 노드와 연결된 다른 인접한 노드들을 확인
		for (int i = 0; i < graph[now].size(); i++) {
			// cost = now 노드까지의 총 길이 + now 와 연결된 간선 길이
			int cost = dist + graph[now][i].second;

			// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
			if (cost < d[graph[now][i].first]) {
				d[graph[now][i].first] = cost;
				pq.push(make_pair(-cost, graph[now][i].first));
			} 
		}
	}
}


int main(void) {
	cin >> n >> m >> start;

	// 모든 간선 정보를 입력받기
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		// x번 노드에서 y번 노드로 가는 비용이 z라는 의미
		graph[x].push_back({ y,z });
	}

	// 최단 거리 테이블을 모두 무한으로 초기화
	fill(d, d + 30001, INF);

	// 다익스트라 알고리즘을 수행
	dijkstra(start);

	// 도달할 수 있는 노드의 개수
	int count = 0;
	// 도달할 수 있는 노드 중에서, 가장 거리가 먼 노드와의 최단 거리
	int maxDistance = 0;
	for (int i = 1; i <= n; i++) {
		// 도달할 수 있는 노드인 경우
		if (d[i] != INF) {
			count += 1;	// 도달 가능한 노드 갯수를 ++
			maxDistance = max(maxDistance, d[i]);	// 도달 가능 노드까지의 거리중 길이가 더 긴 것으로 셋
		}
	}

	// 시작 노드는 제외해아 하므로 count-1 을 출력
	cout << count - 1 << ' ' << maxDistance << '\n';


}

 

우선순위 큐를 사용해서 풀었다. 

우선순위 큐는 기본이 내림차순이므로 길이가 짧은 경로가 top에 오게 하기 위해서 거리에 '-'를 붙인 후, pq에 넣었다.

 

pq에 들어가는 {거리, 노드}와 dist, cost전부 간선 그 하나를 말할 때도 있지만 결론적으론 경로 길이를 말하는 것이다. 

간선 하나의 길이를 특정해서 말하는 것은 graph에 저장되는 {노드, 거리}의 '거리'뿐이다. 

 

dijkstra 함수에서 while문 안의 for문은 다익스트라 알고리즘이 그리디 알고리즘 성격을 띠기 때문에 필요한 과정이다. 

해당 for문의 역할은 now 까지 최단 경로를 구했으면 그 경로에서 now와 연결된 다른 노드들을 찾는것이다. 

 

따라서 d[now]와 dist의 차이를 아는 것이 중요하다.

while문은 pq에서 top에 있는 {경로 길이, 목적지 노드}를 빼와서

경로 길이를 dist에 저장하고, 목적지 노드를 now에 저장한다. 

 

d[now]는 now까지 최단 경로 길이다.

dist는 현재 선택된 경로의 길이 즉, now까지 거리이다. 

 

 

 

[다른 예시 풀이 과정]

이런식으로 진행된다.