💎 문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
💎 입력
첫째 줄에 정점의 개수 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 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
ex)
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
💎 출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
ex)
0
2
3
7
INF
💎 풀이 방법
다익스트라를 이용하여 가중치가 최소가 되는 최단 경로를 구하는 것이다!! 다익스트라는 dp를 이용한 것으로 대표적인 최단경로를 구하는 알고리즘이다. 특정 하나의 정점에서 다른 정점으로 가는 최단 경로를 구하는 것으로 알 수 있다.
하나의 최단 거리에서 그 다음 최단 거리를 구할 때 이전에 구해놓은 최단 거리를 사용한다는 점에서 dp와 유사한 것으로 알 수 있다!!
문제에서는 방향그래프에서 시작점이 주어지고 그 시작점에서 각 정점으로 갈 수 있는 최단 거리를 구해내는 것이 있다. 이에 다익스트라를 활용하여 두 가지 방법을 생각할 수 있는데, 배열을 이용한 동적프로그래밍과 힙구조를 이용한 것이 있다. 근데 배열을 이용하면 알다시피 시간복잡도가 좋지 않다. n^2의 시간복잡도가 나올 것이기 때문에 힙구조를 이용하여 시간복잡도의 효율을 증가시키는 것이 좋다!! 저번 최소 힙 문제에서와 같은 우선순위 큐를 사용하는 것이 좋다!!
for(int i = 1;i <= E;i++){
int temp1, temp2;
int w;
cin >> temp1 >> temp2 >> w;
graph[temp1].push_back({temp2, w});
}
fill(shortestPath, shortestPath + 20001, INF);먼저 INF를 각 정점에 해당하는 최단 경로에 초기화해주는 것이 중요하다! 각 정점에 해당하는 최단 경로는 dp와 마찬가지로 queue를 탐색하면서 이전 값을 사용할 것이기 때문에 INF에 해당하는 값들을 하나씩 바꿔주고 줄여나가 줄 것이다. pair을 이용한 vector를 사용하여 각 인덱스에 해당하는 정점들의 간선에 해당하는 정점의 가중치를 pair로 저장하고 이들을 우선순위 큐에 넣어가면서 최단 경로를 탐색한다!
void dijkstra(int start){
priority_queue <pair<int, int>> pq;
pq.push({0, start});
shortestPath[start] = 0;
while(!pq.empty()){
int cost = -pq.top().first;
int now = pq.top().second;
pq.pop();
if(shortestPath[now] < cost)
continue;
for(int i = 0;i < graph[now].size();i++){
int distance = cost + graph[now][i].second;
if(distance < shortestPath[graph[now][i].first]){
shortestPath[graph[now][i].first] = distance;
pq.push(make_pair(-shortestPath[graph[now][i].first], graph[now][i].first));
}
}
}
}다익스트라의 코드를 살펴보면 priority_queue를 pair을 이용하여 선언하고 first는 가중치의 값, second는 이에 이어진 정점을 넣어줄 것이다. 최단경로의 값들을 넣어주는 배열을 이용하여 정점에 따라서 가중치들을 계산해내갈 것이다.
우선순위 큐가 비어있지 않은 동안 최단경로가 계산된 가중치(-pq.top().first)와 현재 정점(pq.top().second)을 이용하여 가중치의 값이 최단 경로로 구해진 값보다 작을 경우 업데이트 해주기 위해 함수를 반복할 것이다.
정점에 연결된 간선들을 for문으로 반복해주면서 처음 입력받은 vector의 정점에 해당하는 연결된 간선의 다음 정점과 가중치들을 이용하여 이전에 구해진 최단경로와 앞서 계산된 가중치와 정점에 연결된 가중치의 합보다 작다면 이를 최단경로의 값들을 넣어주는 배열에 다시 업데이트해준다. 그리고 우선순위 큐에 다음 정점을 넣어주면서 다른 정점들을 순회할 때 최단 경로를 구해줄 수 있게 하는 것이다!!
다소 우선순위 큐를 이용한 다익스트라의 코드가 어려웠는데 dp를 생각하면서 이전까지 구해진 최단경로를 다음 정점을 이동하였을 때 그 간선의 가중치를 합한 것이 작은지를 비교해준다고 기억하면 될 것 같다!!
문제의 입력값으로 나타낸 그래프를 이용하여 1에서 4로 이동하는 최단 경로를 구해보면 위의 그림과 같다!! 1에서 2로가는 경로를 통해 2까지 가는 최단 경로 2와 3까지 가는 최단경로 3을 처음에 업데이트 하였다면, 4로 이동하는 최단경로가 있다. 이에서 4로 이동하는 경로는 1에서 한번에 없기 때문에 2와 3의 정점에서 가는 방식으로 최단경로를 구하는 것이다. 코드에 따라서 2와 5를 합한 경로가 3을 이동하는 경로보다 작기 때문에 먼저 업데이트 되었다면 이후 3의 정점을 통해 4로 가는 경로로 최단 경로를 구했을 때 이보다 작기 때문에 continue되어 그냥 넘어가질 것이다!!
💎 전체 코드
#include <iostream>
#include <queue>
#include <vector>
#define INF 987654321
using namespace std;
vector<pair<int, int> > graph[20001];
int V, E, K;
int shortestPath[20001];
void dijkstra(int start){
priority_queue <pair<int, int>> pq;
pq.push({0, start});
shortestPath[start] = 0;
while(!pq.empty()){
int cost = -pq.top().first;
int now = pq.top().second;
pq.pop();
if(shortestPath[now] < cost)
continue;
for(int i = 0;i < graph[now].size();i++){
int distance = cost + graph[now][i].second;
if(distance < shortestPath[graph[now][i].first]){
shortestPath[graph[now][i].first] = distance;
pq.push(make_pair(-shortestPath[graph[now][i].first], graph[now][i].first));
}
}
}
}
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> V >> E;
cin >> K;
for(int i = 1;i <= E;i++){
int temp1, temp2;
int w;
cin >> temp1 >> temp2 >> w;
graph[temp1].push_back({temp2, w});
}
fill(shortestPath, shortestPath + 20001, INF);
dijkstra(K);
for(int i = 1;i <= V;i++){
if(shortestPath[i] == INF)
cout << "INF\n";
else
cout << shortestPath[i] << "\n";
}
return 0;
}💎 고민
다익스트라에 대한 알고리즘을 처음 풀어봤는데 이 역시 2학년 자료구조 시간과 3학년 알고리즘 수업시간에 처음 접해보았었다. 시간복잡도를 항상 고려하면서 효율적인 코드를 작성해야하기 때문에 다익스트라의 힙구조를 이용하여 풀어냈던 문제이다. 다익스트라에 대한 내용은 검색을 통해 공부하였고 이를 코드에서 비슷하게 적용시켜서 쉽게 풀었던 문제이다!! 우선순위 큐가 저번 최소 힙 문제에 이어서 요긴하게 쓸 수 있음을 확인할 수 있었다!! 우선순위 큐를 반드시 기억하고 사용하도록 해보장.
다음번에 다익스트라를 이용하는 문제를 다시한번 확인해야겠다!!
화팅!!
