문제 정의
- 문제유형
- 한개의 노드에서 다른 노드까지의 최소 비용 구할때
- 한 노드에서 다른 노드까지 최소비용을 구하는 문제라면 다익스트라를 사용하는 것이 이득
- Floyd를 사용할경우 O(V^3)
- 다익스트라 : O(ElgE)
- 한개의 노드에서 다른 노드까지의 최소 비용 구할때
문제 접근
시작 노드에서부터 나머지 노드까지의 거리 배열을 무한대값으로 초기화(dist 배열)
- dist배열의 시작 노드값을 0으로 만듬
시작 노드 연결된 간선을 모두 우선순위 큐에 넣음
우선순위 큐가 가지고 있는 가장 작은 간선을 꺼냄
이 간선을 통할경우 기존의 거리 값보다 작아질때, 해당 노드에 연결된 간선을 우선순위 큐에 추가
위 과정을 우선순위 큐가 empty될때까지 반복
시간복잡도
모든 간선을 우선순위 큐에 넣음 : ElgE
대표예제 : 백준 1913 최소비용 구하기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <iostream> #include <queue> #include <vector> using namespace std; const int inf = 1e8+10; // 시작점에서부터 해당 노드까지의 거리 int dist[1010]; // 인접 간선 리스트 vector<pair<int, int>> adj[1010]; int main() { ios::sync_with_stdio(0); cin.tie(0); // 거리 배열 무한값으로 초기화 fill(dist, dist+1010, inf); int N,M; cin >> N >> M; while(M--) { int a,b,c; cin >> a >> b >> c; adj[a].push_back(make_pair(c,b)); } int st, en; cin >> st >> en; // 시작 노드는 거리 0 dist[st] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push(make_pair(dist[st], st)); while(!pq.empty()) { auto eq = pq.top(); pq.pop(); int ec = eq.first; int ei = eq.second; // 같은 노드에 대한 간선 중, 이미 더 작은 값으로 업데이트 된경우 if(dist[ei] != ec) continue; for(auto x : adj[ei]) { int nc = x.first; int ni = x.second; if(dist[ni] > ec + nc) { dist[ni] = ec + nc; pq.push(make_pair(dist[ni], ni)); } } } cout << dist[en] << '\n'; return 0; } | cs |
문제 유형
- 다익스트라 경로 구하기 : https://www.acmicpc.net/problem/11779
- 거꾸로 다익스트라 : https://www.acmicpc.net/problem/1238
- 2차원 다익스트라 : https://www.acmicpc.net/problem/4485
- 한점 거치는 다익스트라 : https://www.acmicpc.net/problem/18223
'알고리즘 > 개념' 카테고리의 다른 글
[알고리즘] Segment Tree, 세그먼트 트리 알고리즘 (0) | 2021.02.14 |
---|---|
[알고리즘] Bellman Ford, 벨만 포드 알고리즘 (0) | 2021.02.14 |
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘 (0) | 2021.02.08 |
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리 (0) | 2021.02.08 |
[알고리즘] 문자열 KMP, Rabin Karp (0) | 2021.02.07 |