https://www.acmicpc.net/problem/1753
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가
www.acmicpc.net
해당문제는 다익스트라 알고리즘을 Heap을 이용하여 구현하는 문제이다.
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<pair<int, int>> matrix[20005];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int result[20005];
int INF = 999999;
void dijkstra(int start) {
result[start] = 0;
pq.push(make_pair(0, start));
while (!pq.empty()) {
int cur = pq.top().second;
int cost = pq.top().first;
pq.pop();
int size = matrix[cur].size();
for (int i = 0; i < size; i++) {
int next = matrix[cur][i].second;
int newCost = matrix[cur][i].first + cost;
if (result[next] > newCost) {
result[next] = newCost;
pq.push(make_pair(newCost, next));
}
}
}
}
int main(void) {
int n, e;
cin >> n >> e;
/* init cost array */
for (int i = 0; i <= n; i++)
result[i] = INF;
int start;
cin >> start;
for (int i = 0; i < e; i++) {
int u, v, c;
cin >> u >> v >> c;
matrix[u].push_back(make_pair(c,v));
}
dijkstra(start);
for (int i = 1; i <= n; i++) {
if (result[i] == INF) cout << "INF\n";
else cout << result[i] << "\n";
}
}다익스트라 알고리즘은 한 점에서부터 다른 노드로의 경로의 최소 값을 구하는 알고리즘이다.
다익스트라의 과정으로는 다음과 같다.
1. 시작 노드는 비용을 0으로 설정한다.
2. 시작 노드를 기준으로 비용 초기값을 설정한다. (인접한 값은 해당 가중치로, 인접하지 않았다면 무한대로)
3. 비용값 중 방문하지 않았고 비용 중 가장 작은 값을 다음 노드로 선택, 방문한다.
4. 선택된 노드까지의 비용 + 선택된 노드에서 인접한 노드로의 경로 비용 vs 인접한 노드의 비용을 비교하여 더 값싼 비용을 선택, 인접 노드로의 경로 비용을 갱신한다.
5. 3번으로 돌아가 반복한다.
여기서 3~4번의 과정을 효율적으로 수행하기 위하여 Heap 구조를 사용한다.
* priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
priority_queue의 경우 기본적으로 less, 즉 내림차순 정렬이다.
위와 같은 선언을 통하여 Min Heap으로 선언 가능하다.
* #include<utility>의 pair를 활용하여 인접 리스트 방식으로 구현이 가능하다.
* pair를 활용한 priority_queue의 비교 순서는 first, second 순서로 비교한다.
'백준 온라인 저지 - 단계별로 풀어보기 > 그래프' 카테고리의 다른 글
| 11724 - 연결 요소의 개수 (0) | 2021.08.24 |
|---|
