8. 다익스트라 알고리즘
푼 문제와 정답 코드는 해당 링크 참고
문제) 백준 1853
다익스트라 알고리즘 활용
8.1. 접근 과정_1
1) 다익스트라 알고리즘을 활용할 때, 마지막에 출력하는 배열 d에 '시작점으로 각 노드까지로 가는 거리의 최소값'을 대입하는 것을 이해했었다.
2) 따라서, 배열 d를 2차원 배열로 생성한다.
3) d에 시작점 ~ i까지 가는 값이 생성되면 해당 노드로의 d의 거리 값을 바로 대입하지 않고, 누적해서 가져온다(2차원 배열 이용)
4) 마지막에 k번째 값을 출력한다.
→ 시간초과가 발생한다. d[i]에서 k번째 값을 빼기 위해서는 해당 부분의 d[i][0~] 부분을 정렬해줘야 하기 때문으로 예측할 수 있었다.
8.2. 접근 과정_2
d에 선언한 배열에 우선순위 큐(priority queue)를 활용한다.
→ 시간을 많이 활용했는데 스스로는 구현이 힘들었다.
결국 책과 구글링을 보았는데,
접근 방법은 사람마다 사용 수단이 다를 뿐이지, 방식은 비슷했다. 우선순위 큐에 대한 공부가 더 필요할 것 같았다.
if 조건문은 앞서 접근_1에서 사용했던(결과 구현은 못했지만) if문 조건과 구글링을 활용하며 d에서의 각 배열의 크기를 제한하였다. 막혔던 부분은 우선순위 큐 배열의 크기 제한과 .top(), .pop()을 적절히 사용하여 해결할 수 있었다.
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>
using namespace std;
int INF = 2147000000;
int k;
// 간선 정보를 저장하는 벡터
vector<pair<int, int>> a[1001];
// 최단 거리를 저장하는 벡터
// vector<int> d(20001);
priority_queue<int> d[1001];
// 초기화는 선언 시 자동으로 이뤄지고, 별도의 초기화가 필요하지 않다.
// 다익스트라 실행 함수
void dijkstra(int startIndex) {
// min heap 구조, 더 작은 값을 기준으로 최상단 노드를 만들도록 한다.
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 시작점에서 시작점으로의 최소 거리는 0
d[1].push(0);
// 출발 노드의 정보를 우선순위 큐에 넣는다.
pq.push(make_pair(0, startIndex));
while (pq.empty()==false) {
// 기준 점부터 가장 최소 거리 노드의 index
int current = pq.top().second;
// 기준 점부터 가장 최소 거리 노드의 값
int distance = pq.top().first;
pq.pop();
for (int i = 0; i < a[current].size(); i++) {
// 선택된 노드의 인적노드
int nextIndex = a[current][i].first;
// 선택된 노드를 거쳐서 인접 노드로 가는 거리
int nextDistance = distance + a[current][i].second;
//int nextDistance = a[current][i].second;
// 여기서 달라지는데,
// 최소 거리에 대한 저장 공간을 우선순위 큐로 만들었으니까,
// k번째의 값을 계속 갱신하도록 한다.
if (d[nextIndex].size() < k) {
d[nextIndex].push(nextDistance);
// 그렇게 새롭게 갱신된 값을 넣어준다.
pq.push(make_pair(nextDistance, nextIndex));
}
else if (d[nextIndex].top() > nextDistance) {
d[nextIndex].pop();//해당 경로에서 k번째인 경우를 삭제시킴
d[nextIndex].push(nextDistance);
pq.push(make_pair(nextDistance, nextIndex));
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
//int k;
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int start, end, cost;
cin >> start >> end >> cost;
a[start].push_back(make_pair(end, cost));
}
dijkstra(1);//dijkstra(0);
for (int i = 1; i <= n; i++) {
if (d[i].size() < k) {
cout << "-1" << "\n";
}
else {
cout << d[i].top() << "\n";
}
}
return 0;
}
그래도 구현 능력이 조금 더 상승한 것 같다.
다익스트라 알고리즘 이해에서 시간을 쏟은 보람이 있는 듯..
@sonyrainy