[알고리즘] 백준 1753번: 최단경로 (C++), 다익스트라

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

1753번: 최단경로

(https://yabmoons.tistory.com/364)

이번 포스팅은 링크에 걸어둔 다익스트라 포스팅을 정리한 포스팅으로 자세한 설명은 링크에 되어있다.

 

[다익스트라 개념 정리]

시작 노드 -> 도착 노드로 가는 최소 비용(가중치)을 구하는 알고리즘

1. 첫 노드 방문 체크
2. 방문한 노드와 연결되어 있는 노드들 거리 업데이트
3. 방문한 노드와 연결된 노드들 중 '비용이 가장 적게 드는 노드' 선택 (이게 포인트 같다)
4. 해당 정점 방문 체크
5. 4번으로 인해 방문 체크되어있는 노드에서 새롭게 갱신될 수 있는 노드들 거리 갱신
6. 2~5 과정 반복

+ '비용이 가장 적게 드는 노드'를 방문 체크하고, 다시는 봐도 되지 않는 이유가 신기하다.
비용이 가장 적게 들기 때문에 현재 노드에서 제일 짧은 거리라고 볼 수 있다.
그러므로 다른 경로로 돌아서 오더라도 더 짧은 거리가 될 수 없다.
단, 비용이 음수가 아니라서 가능한 소리다.

비용이 음수라면 '비용이 가장 적게 드는 노드'가 최소 비용 경로가 아니게 되는 경우가 존재하기 때문이다.

그래서, 다익스트라 알고리즘은 모든 경로의 가중치가 양수일 때만 가능하다.

 

시간 복잡도가 다른 두 가지 방법 알고리즘 (N == 정점의 개수, E == 간선의 개수)

1. 배열을 사용한 다익스트라: O(N^2)
2. 우선순위 큐를 사용한 다익스트라: O(E * logN)

[1. 배열을 사용한 다익스트라]

#include <iostream>
#include <vector>
#define MAX 20001
#define INF 987654321
using namespace std;

int V, E, K;
int map[MAX][MAX];
int dist[MAX];
bool visited[MAX];

void upDateDist(int node) {
	for (int i = 1; i <= V; i++) {
		if (visited[i]) {
			continue;
		}

		if (dist[node] + map[node][i] < dist[i]) {
			dist[i] = dist[node] + map[node][i];
		}
	}
}

int find_Shortest_Node() {
	int minDist = INF;
	int minIdx = -1;
	for (int i = 1; i <= V; i++) {
		if (visited[i]) {
			//이미 방문한 거라면 패스
			continue;
		}

		if (dist[i] < minDist) {
			// 다익스트라 함수에서 갈 수 있는 거리를 갱신했기 때문에 가능
			minDist = dist[i];
			minIdx = i;
		}
	}
	return minIdx;
}

void dijkstra() {
	for (int i = 1; i <= V; i++) {
		// 시작 노드에서 갈 수 있는 노드 사이에 거리 갱신

		// 갈 수 있는 노드라면 입력 받은대로 거리를 업데이트 하지만
		// 갈 수 없다면 INF로 초기화 했기에 INF가 됨.
		dist[i] = map[K][i];
	}

	dist[K] = 0;
	visited[K] = 1;

	for (int i = 0; i < V - 1; i++) { // (노드 개수 - 1)만큼 반복
		// (노드 개수 - 1)인 이유 >> 시작 노드는 이미 방문처리 함
		int newNode = find_Shortest_Node();

		if(newNode < 0) {
        	// -1이 newNode로 리턴되는 경우
			continue;
		}
		visited[newNode] = 1;
		upDateDist(newNode);
	}
}

int main() {
	cin >> V >> E >> K;
	for (int i = 1; i <= V; i++) {
		// 모든 거리 INF로 초기화
		dist[i] = INF;

		for (int j = 1; j <= V; j++) {
			if (i == j) {
				// 자기 자신에게 갈 수 있는 비용 0
				map[i][j] = 0;
			}
			else {
				// 그 외의 거리 INF로 초기화
				map[i][j] = INF;
			}
		}
	}

	for (int i = 0; i < E; i++) {
		// 간선에 대한 비용 입력
		int a, b, c;
		cin >> a >> b >> c;
		map[a][b] = c;
	}

	dijkstra();

	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF) {
			cout << "INF" << '\n';
		}
		else {
			cout << dist[i] << '\n';
		}
	}

	return 0;
}

[2. 우선순위 큐를 사용한 다익스트라]

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#define MAX 20001
#define INF 987654321
using namespace std;

int V, E;
int K;
int dist[MAX];
vector<pair<int, int>> graph[MAX];

struct cmp {
	// 가중치(second)가 더 작은 걸 우선적으로
	bool operator()(pair<int, int>& a, pair<int, int>& b) {
		return a.second > b.second;
	}
};

void dijkstra() {
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	pq.push(make_pair(K, 0));
	dist[K] = 0;
	
	while (!pq.empty()) {
		int now = pq.top().first;
		int cost = pq.top().second;
		pq.pop();

		if (dist[now] < cost) {
			continue;
		}

		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int nextCost = graph[now][i].second;

			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push(make_pair(next, dist[next]));
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> V >> E;
	cin >> K;
	for (int i = 1; i <= E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
	}

	for (int i = 1; i <= V; i++) {
		// 각 정점으로 갈 수 있는 거리 INF로 초기화
		dist[i] = INF;
	}

	dijkstra();

	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF) {
			cout << "INF" << '\n';
		}
		else {
			cout << dist[i] << '\n';
		}
	}

	return 0;
}