백준 1753번: 최단경로

 

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

1753번: 최단경로

문제를 풀기 위해 알아야 하는 것

1. 우선순위 큐

2. 다익스트라 알고리즘 + 개선된 다익스트라 알고리즘

 

1. 우선순위 큐

1.1. Queue ( 큐 )

FIFO(First In, First Out : 먼저 들어온것이 먼저 나간다.) 의 형식을 취하는 자료구조 이다.

 

 

1.2. Priority Queue ( 우선순위 큐 )

들어오는 순서에 상관없이 우선순위가 높은 요소가 먼저 나가는 자료구조 이다.

 

min-priority-queue

 

2. 다익스트라 + 개선된 다익스트라

2.1. 다익스트라 알고리즘

최단경로를 탐색하는 알고리즘 중 하나이다.

특정한 하나의 정점을 시작 정점으로 놓았을때 이 정점에서 시작해서 다른 모든 정점으로 가는 최단 경로를 탐색한다.

다이나믹 프로그래밍을 활용한다는 특징이 있다.

 

2.2. 다익스트라 알고리즘 과정

1. 시작 정점에서 시작정점의 경로는 0으로 나머지는 INF(무한대)로 설정한다.

2. 시작정점에서 인접한 정점으로의 경로를 갱신하고 탐색을 완료 했음을 저장한 후, 시작 정점으로 부터 거리가 가장 짧은 정점으로 이동한다.

3. 이동한 정점과 인접한 정점으로의 경로를 갱신하고 탐색을 완료 했음을 저장한 후,  시작 정점으로 부터 거리가 가장 짧은 정점으로 이동한다.

4. 3번 과정을 모든 정점을 탐색할때 까지 반복한다.

 

2.3. 개선된 다익스트라 알고리즘(1753번의 해답)

위에서 설명한 다익스트라 알고리즘은 모든 정점에 대해 각 정점과의 간선의 거리를 비교해야하기 때문에 시간복잡도가 다음과 같다.

$$ O(V^2) (V: 정점의 개수)$$

하지만 우선순위 큐를 이용하여 구현하면 이를 개선시킬수 있다. 이를 개선된 다익스트라 알고리즘이라고 하며 min-heap을 이용해 구현한 우선순위 큐를 사용해 시간복잡도를 다음과 같이 줄일수 있다.

$$ O(ElogE) (E: 간선의 개수) $$

2.3.1.  과정

1. 시작 정점에서 시작정점으로의 거리는 0으로 나머지 정점까지의 거리는 INF(무한대)로 초기화 한 뒤, 거리는 0 정점은 시작정점인 데이터를 우선순위 큐에 PUSH한다.

2. 큐에서 우선순위가 가장 높은 데이터를 POP하며 해당 정점과 연결된 정점을 찾고 시작정점에서 해당 정점까지의 거리를 비교한후 저장되어있는 거리보다 거리가 짧다면 이를 갱신한후 해당 정보를 우선순위 큐에 PUSH한다.

3. 2번 과정을 우선순위 큐에 어떤 데이터도 남아있지 않을 때 까지 반복한다.

 

2.2.2. 개선된 다익스트라 알고리즘의 시간 복잡도

우선순위 큐에서 POP한 정점과 연결된 간선을 모두 확인하며  이때 우선순위 큐에서 데이터를 넣고 빼는 과정으로 모든 정점을 탐색하기 때문에 간선을 모두 확인할때 E, 우선순위 큐에서 데이터를 넣고 뺄때 logE 만큼 반복하기 때문에 시간 복잡도는 다음과 같다. 

$$ O(ElogE) $$

중복 간선이 없는 경우에는 시간 복잡도를 다음과 같이 표현하는 것도 가능하다.

$$ O(ElogV) $$

 

3. BOJ 1753번 해답

#include <bits/stdc++.h>

#define INF 987654321

using namespace std;

vector<pair<int, int> > nodes[20001];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >
    pq;

int dists[20001];

void solve(int start) {
  pq.push(make_pair(0, start));
  dists[start] = 0;
  while (!pq.empty()) {
    int dist = pq.top().first;
    int node = pq.top().second;
    pq.pop();

    for (int i = 0; i < nodes[node].size(); i++) {
      int n = nodes[node][i].first;
      int w = nodes[node][i].second;

      if (dist + w < dists[n]) {
        dists[n] = dist + w;
        pq.push(make_pair(dists[n], n));
      }
    }
  }
}

int main() {

  int V, E, K;
  cin >> V >> E;
  cin >> K;

  for (int i = 1; i <= V; i++) {
    dists[i] = INF;
  }

  int u, v, w;
  for (int i = 0; i < E; i++) {
    cin >> u >> v >> w;
    nodes[u].push_back(make_pair(v, w));
  }

  solve(K);

  for (int i = 1; i <= V; i++) {
    if (dists[i] == INF) {
      cout << "INF\n";
    } else {
      cout << dists[i] << "\n";
    }
  }

  return 0;
}