[c++] 백준 1753 - 최단경로(다익스트라, dijkstra, priority queue, BFS)

0. [c++] 백준

https://www.acmicpc.net/problem/1753

1. 풀이

음... 문제를 풀기 위해서 4일가량을 이리저리 뒤지면서 공부를 하게 되었던 문제였다.

우선, 최단거리를 계산하기 위해서 적합한 방식은 무엇일까? 하면 기본적으로 BFS의 방식이 될 수 있겠다.

여기서 다익스트라라는 방식은 이 BFS방식에 이전에 사용했었던, priority queue를 활용해서 더 짧은 간선이 존재하면 그 곳을 먼저 탐색을 하는 형식으로 구성되는 방식의 구현이었다.

이때, 밑의 코드(1번째 구현)에서 가중치를 넣고 빼는 부분을 보면 음수 형태로 넣어주고, 꺼낼때 양수로 다시 변환해서 사용하는 것을 확인 할 수 있는데, 이렇게 하는 이유는 그냥 구현을 하게되면 복잡한 우선순위 큐를 선언해야 하기 때문이다.

이렇게 하지 않는다면, priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;라고 선언을 해야한다.

또한 queue에서 꺼낸 위치의 거리가 이미 찾은 수보다 짧은 경우 무시하도록 설계를 하였다.

이는 priority queue를 활용한 핵심과도 같은데, 큐에 수가 들어가는 경우를 살펴보면, dist[there]가 변하는 경우에 이를 queue에 집어넣게 되어있는데, 이 집어넣는 것은 다른 탐색에서 더 짧은 결과가 구해지면 큐에 들어있는 것이 무시되도록 설계를 한 것이다.

1번째 코드의 시간 복잡도는 O(ElgV)가 되고

2번째 코드의 시간 복잡도는 O(V^2 + E)가 된다.(E는 간선의 개수)

2. 소스코드

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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

#include<iostream> #include<vector> #include<queue>   using namespace std;     const int MAX_V = 20001; const int INF = 1000000007; //정점의 개수 int V; //그래프의 인접 리스트. (연결된 정점 번호, 간선 가중치)쌍을 담는다. vector<pair<int, int> > adj[MAX_V]; bool visited[20001];     vector<int> dijkstra(int src) {     vector<int> dist(V + 1, INF);     dist[src] = 0;     priority_queue<pair<int, int> > pq;     pq.push(make_pair(0, src));     while (!pq.empty()) {         int cost = -pq.top().first;         int here = pq.top().second;         pq.pop();         //만약 지금 꺼낸 것보다 더 짧은 경로를 알고 있다면 지금 꺼낸 것을 무시한다.         if (dist[here] < cost) continue;         //인접한 정점들을 모두 검사한다.         for (int i = 0; i < adj[here].size(); i++) {             int there = adj[here][i].first;             int nextDist = cost + adj[here][i].second;             //더 짧은 경로를 발견하면, dist[]를 갱신하고 우선순위 큐에 넣는다.             if (dist[there] > nextDist) {                 dist[there] = nextDist;                 pq.push(make_pair(-nextDist, there));             }         }     }     return dist; }   vector<int> dijkstra2(int src) {     vector<int> dist(V+1, INF);     //각 정점을 방문했는지 여부를 저장한다,     vector<bool> visited(V, false);     dist[src] = 0; visited[src] = false;     while (true) {         //아직 방문하지 않은 정점 중 가장 가까운 정점을 찾는다.         int closest = INF, here;         for (int i = 0; i < V; i++)              if (dist[i] < closest && !visited[i]) {                 here = i;                 closest = dist[i];             }         if (closest == INF) break;         //가장 가까운 정점을 방문한다.         visited[here] = true;         for (int i = 0; i < adj[here].size(); i++) {             int there = adj[here][i].first;             if (visited[there]) continue;             int nextDist = dist[here] + adj[here][i].second;             dist[there] = min(dist[there], nextDist);         }     }     return dist; }         int main() {     ios_base::sync_with_stdio(0);       cin.tie(0);           int N, a, b, k, start;     cin >> V >> N;     cin >> start;     for (int i = 0; i < N; i++) {         cin >> a >> b >> k;         adj[a].push_back({ b, k });     }     vector<int> ret = dijkstra2(start);     for (int i = 1; i <= V; i++) {         if (ret[i] == INF)             cout << "INF" << endl;         else             cout << ret[i] << endl;     }   } Colored by Color Scripter

cs

3. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.923~930.

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!