[백준] No.1854 - K번째 최단경로 찾기 (C++, 다익스트라)

문제

 

www.acmicpc.net/problem/1854

1854번: K번째 최단경로 찾기

 

풀이

 

solved.ac 난이도: Platium 5

 

다익스트라 최단 경로 알고리즘을 잘 이해해야 풀 수 있는 고난도 문제.

일단 풀이는 다음과 같다.

 

우선순위 큐를 각 정점마다 하나씩 가지도록 하고(우선순위 큐의 배열을 생성)

해당 정점을 방문할 때마다 그때의 dist(cost, 소요시간)를 우선순위 큐에 push하여 저장한다.

 

1. 해당 정점의 우선순위 큐의 크기가 K개 이하인 경우

소요시간을 정점의 우선순위 큐에 push하고

다익스트라를 진행하는 전체 우선순위 큐(이하 pq)에도 push한다.

 

2. 해당 정점의 우선순위 큐의 크기가 K개인 경우

정점들의 우선순위 큐는 다익스트라의 pq와 다르게 내림차순으로

즉, 큰 수가 top에 오도록 구성해야 한다.

만약 새로 구한 정점으로의 소요시간(next_cost)이 해당 정점의 pq의 top보다 작다면 top의 수는 K번째 최단 경로가 될 수 없다.

따라서 top을 pop 해주고, next_cost를 push 해준다.

 

그 후 next_cost를 다익스트라의 pq에 push하여 해당 경로로부터 다른 경로로 나아갈 수 있게 해주자.

 

 

vector<ll> Dijkstra(int start_city){
  priority_queue<pair<ll,int>, vector<pair<ll,int>> ,greater<pair<ll,int>> > pq;
  vector<priority_queue<ll>> dist(city_num+1);
 
  pq.push({0, start_city});
  dist[start_city].push(0);
 
  int next_city, now_city;
  ll next_cost, cost; 
  while(!pq.empty()){
    now_city = pq.top().second;
    cost = pq.top().first;
    pq.pop();
 
    for(int i=0; i<adj[now_city].size() ; ++i){
      next_city = adj[now_city][i].second;
      next_cost = cost + adj[now_city][i].first;
 
      if(dist[next_city].size() <K){
        dist[next_city].push(next_cost);
        pq.push({next_cost, next_city});
      }else if(dist[next_city].top() > next_cost){  //K개가 우선순위 큐에 존재 하지만 next_cost가 top보다 작은 경우 
        dist[next_city].pop();
        dist[next_city].push(next_cost);
        pq.push({next_cost, next_city});
      }
      
    }
  }
 
  vector<ll> ret(city_num+1,-1);
  for(int i=1; i<= city_num ; ++i)
    if(dist[i].size() == K) //우선순위 큐가 채워지지 않은 정점은 K번째 경로가 
      ret[i] = dist[i].top();
  
  return ret;
}

 

 

 

처음에 풀이를 보고 어떻게 이것만으로 K번째 최단 경로를 구할 수 있는지 의아했다.

해당 정점들의 pq가 채워지고 난 후에는 더 이상 다익스트라의 전체 pq에 값을 push하지 않았기 때문이다.

 

따라서 다음과 같이 이미 K번째 최단 경로를 채운 정점 u가 있다고 생각해보았다.

K번째 최단 경로를 모두 채운 u에서는 전체 pq에 더 이상 값을 push하지 않는다.

그런데 만약 u정점에서만 나아갈 수 있는 1,2번 노드는 아직 k-3, k-5번째 최단 경로만 채워졌다면

1,2번 노드는 더이상 전체 pq에 u가 없으므로 접근할 수 없다.

따라서 K번째 경로까지 우선순위 큐를 채울 수 없다.

K번째 경로를 채웠더라도 전체 pq에는 값을 push 해야 되는 것 아닐까?

 

 

 

하지만 생각해보면 이런 경우는 발생할 수 없다.

u가 이미 K번째 최단 경로를 채웠다면 전체 pq에 이 u정점의 K개의 cost가 push 되었을 것이고

그에 따라 1,2번 노드로 가는 K개의 경로가 생성되었을 것이다.

따라서 1,2번 정점의 경로가 u보다 적게 생성될 경우는 없다.

또한 u로의 K개의 최단 경로에서 생성되는 1, 2번 경로 또한 그들의 최단 경로가 될 수밖에 없다. 

 

그러므로 이미 K개의 최단 경로가 채워진 정점의 pq에는 더 작은 경로가 발견되지 않는 이상 전체 pq에 값을 push할 필요가 없다.

해당 정점에서는 이미 자신이 진입할 수 있는 모든 정점으로의 경로(자신으로부터 최단 경로)를 생성해 주었기 때문이다.

 

 

코드