※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 1753번 문제인 최단경로이다.
문제는 아래 링크를 확인하자.
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.
www.acmicpc.net
이 문제는 다익스트라(Dijkstra) 알고리즘을 구현해보는 문제이다.
개념만 알고 직접 코딩해본 적이 없는 알고리즘이라 이번 기회에 자료를 찾아 구현해보았다.
먼저 각 노드까지의 거리의 배열을 준비한다. 이 때, 시작점을 제외한 모든 점까지의 거리를 도달할 수 없는 큰 수를 미리 넣어준다.
그 다음에는 남은 점중 시작점에서 가장 가까운 점을 찾아 그 점으로부터 다른 점까지의 거리를 그 다른 점까지의 기존 거리와 비교해 갱신한다.
남은 점중 가장 가까운 점을 찾는 것은 priority queue(우선순위 큐)를 이용해 구현할 수 있다. 남아있는 노드 중 시작점과 가장 가까운 노드를 priority queue에서 뽑아 쓰는 방식으로 구현할 수 있기 때문이다. 단, stl에서 제공하는 priority queue는 max heap이므로 최솟값을 받기 위해서는 거리에 -를 붙여서 넣어야 한다.
또한, priority queue에 원소를 넣는 시점 이후로 최단거리가 갱신된다면, priority queue에 갱신된 정보를 그대로 다시 넣고, 만약 priority queue에서 꺼낸 점이 이미 처리된 점이라면, 더 짧은 거리일 때의 데이터를 이미 기록했으므로 건너뛰어줘야 한다. 이를 위해 done 배열을 만들었다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <queue>
using std::vector;
using std::pair;
using std::cin;
using std::cout;
using std::priority_queue;
vector<pair<int, int>> graph[20001];
priority_queue<pair<int, int>> que;
int distance[20001];
bool done[20001];
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int V, E, K;
cin >> V >> E >> K;
for (int i = 1;i <= V;i++) {
distance[i] = 1000000000;
}
distance[K] = 0;
que.push({ 0,K });
for (int i = 0;i < E;i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back(pair<int, int> {v, w});
}
while (!que.empty()) { // Dijkstra
int current = que.top().second; que.pop();
if (done[current]) continue;
done[current] = true;
for (auto u : graph[current]) {
int v = u.first, w = u.second;
if (distance[current]+w<distance[v]) {
distance[v] = distance[current] + w;
que.push({ -distance[v],v });
}
}
}
for (int i = 1;i <= V;i++) {
if (distance[i] == 1000000000) cout << "INF\n";
else cout << distance[i] << "\n";
}
return 0;
}'BOJ' 카테고리의 다른 글
| [BOJ 1916 // C++] 최소비용 구하기 (0) | 2021.02.13 |
|---|---|
| [BOJ 1261 // C++] 알고스팟 (0) | 2021.02.12 |
| [BOJ 14502 // C++] 연구소 (0) | 2021.02.10 |
| [BOJ 2143 // C++] 두 배열의 합 (0) | 2021.02.09 |
| [BOJ 13398 // C++] 연속합 2 (0) | 2021.02.08 |