[백준] 1753 최단경로 (C++)

백준 1753 최단경로 문제
백준 1753 최단경로 소스코드

📄 문제 설명

Problem

방향그래프가 주어지면 시작점으로부터 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오.
(단, 모든 간선의 가중치는 10 이하의 자연수이다.)

Input

첫째 줄 : 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)
(모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다.)
둘째 줄 : 시작 정점의 번호 K(1 ≤ K ≤ V)
셋째 줄 : E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)
(이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 의미)
(u와 v는 서로 다르며 w는 10 이하의 자연수)
(서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.)

Output

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력
시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

Example Input 1

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

Example Output 1

0
2
3
7
INF

📝 문제 해설

이 문제는 제목처럼 최단 경로 문제이다.
최단 경로 문제란 가중 그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제이다.

▶ 최단 경로 문제 종류

- 단일 출발(single-source) 최단 경로
	어떤 하나의 정점에서 출발해 나머지 모든 정점까지의 최단경로를 찾는 문제

- 단일 도착(single-destination) 최단 경로
	모든 정점에서 출발해 특정 하나의 정점까지의 최단경로를 찾는 문제

- 단일 쌍(single-pair) 최단 경로
	어떤 정점 v에서 v'로 가는 최단 경로를 구하는 문제

- 전체 쌍(all-pair) 최단 경로
	모든 정점 쌍들의 사이의 최단 경로를 구하는 문제

▶ 최단 경로 알고리즘

- BFS(완전 탐색 알고리즘)
	가중치가 없거나 모든 가중치가 동일한 그래프에서 최단경로를 구할 때 가장 빠르다

- 다익스트라 알고리즘 (Dijkstra Algorithm)
	음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발 단일 도착의 최단경로 문제

- 벨만-포드 알고리즘 (Bellman-Ford-Moore Algorithm)
	가중 그래프에서의 단일 쌍, 단일 출바르 단일 도착의 최단경로 문제

- 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
	전체 쌍 최단 경로 문제

▶ 다익스트라 알고리즘 (Dijkstra's Algorithm)

V개의 정점과 음수가 아닌 E개의 간선을 가진 그래프 G에서
특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘

◼ 특징
- 각 정점을 최대 한 번씩만 방문하여 최단 거리를 확정한다.
- 아직 방문하지 않은 정점들 중 최단 거리인 점을 찾아 방문하고 최단거리 획정 반복
- 총 V * V번의 연산이 필요해 O(V²)의 시간 복잡도를 가진다.
- 방문하지 않은 정점 중 최단 거리가 최소인 정점을 찾는 과정에서 우선순위 큐 / 힙을 이용하면 더욱 개선된 알고리즘 가능

▶ 문제 해결 방법

1. S(시작점)로부터 정점까지의 거리 벡터 dist 초기화(가장 큰 수로)
2. 인접 행렬(adjList) 초기화
3. 인접 행렬 정보 저장
4. 다익스트라 진행
	1) 출발지 거리를 0으로 초기화 하고 pq에 push
	2) 현재 정점까지의 저장된 거리보다 정점의 cost가 더 큰 경우 Pass
	3) 현재 위치에 연결된 간선 탐색
		1] cost가 더 작은 경우에만 갱신하고 pq에 push
5. 결과 출력

</> Source Code

#include <bits/stdc++.h>
#define INF 1E9

using namespace std;

struct Edge{
	int id;
	int cost;
};

struct Comp{
	bool operator()(const Edge& a, const Edge& b){
		return a.cost > b.cost;
	}
};

vector<vector<Edge>> adjList;
vector<int> dist;

void dijkstra(int start){
	priority_queue<Edge, vector<Edge>, Comp> pq;
	
	// 1)
	dist[start] = 0;
	pq.push({start, dist[start]});
	
	while(!pq.empty()){
		Edge now = pq.top();
		pq.pop();
		
		// 2)
		if(dist[now.id] < now.cost) continue;
		
		// 3)
		int size = adjList[now.id].size();
		for(int i = 0; i < size; i++){
			Edge next = adjList[now.id][i];
			
			// 1]
			if(dist[next.id] > now.cost + next.cost){
				dist[next.id] = now.cost + next.cost;
				pq.push({next.id, dist[next.id]});
			}
		}
	}
}

int main(){	
	int v, e, start;
	scanf("%d %d %d", &v, &e, &start);
	
	// 1. init dist, 2. init adJList
	for(int i = 0; i <= v; i++){
		dist.push_back(INF);
		vector<Edge> tmp;
		adjList.push_back(tmp);
	}	
	
	// 3. input adjList
	for(int i = 0; i < e; i++){
		int a, b, w;
		scanf("%d %d %d", &a, &b, &w);
		adjList[a].push_back({b, w});
	}
	
	// 4. dijkstra
	dijkstra(start);
	
	// 5. print result
	for(int i = 1; i < dist.size(); i++){
		if(dist[i] < INF){
			printf("%d\n", dist[i]);
		}
		else{
			printf("INF\n");
		}
	}
	
	return 0;
}