[백준] No.5719 - 거의 최단 경로 (C++, 다익스트라)

문제

 

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

5719번: 거의 최단 경로

 

풀이

 

solved.ac 난이도: Platium 5

 

 

다익스트라는 기본적으로 최단 경로 값만 구하기 때문에 동일한 최단 경로가 여러 개가 있더라도 결국 하나의 값만 저장이 된다.

이번 문제는 최단 경로들에 사용된 모든 간선을 사용하지 않고(사실상 제거하고) 최단 경로를 구하는 것이다.

 

따라서 정점들의 각각에 우선순위 큐를 사용하여 해당 정점에 최소 cost으로  도달하는 모든 경로를 저장한다.

그 후 우선순위 큐에 저장된 정보를 이용하여 이전 간선들로 역추적하여 경로에 해당하는 간선을 모두 지운다.

이제 모든 최단 경로 간선들은 삭제되었으므로 일반적인 다익스트라로 거의 최단 경로를 구할 수 있다.

 

 

이를 구현하기 위해 다음과 같은 구조체를 사용한다.

 

struct DistInfo{  //최단 거리 정보 저장
  int cost;
  int parent;
  int edge_idx;
 
  bool operator<(const DistInfo& x) const{
    return cost > x.cost;
  }
};

 

parent는 edge_idx 번째 간선을 통해 해당 정점으로 진입하는 정점, 즉 부모 정점(이전 정점)의 idx를 의미한다.

간선의 저장에는 EdgeInfo 구조체를 사용하였다.

 

struct EdgeInfo{  //간선 정보 저장
  int to;
  int cost;
  int edge_idx;
};

 

간선들에 번호를 부여한 이유는 간선을 제거할 때 정점들의 인접 간선을 저장하는 2차원 vector인 

vector<vector<EdgeInfo>> adj에서 해당 간선을 직접 찾아 삭제하는 것보다는 해당 간선이 삭제된 간선인지를 저장하는

bool is_delete[10001] 배열로 나타내는 것이 훨씬 효율적이기 때문이다.

 

이제 최단경로를 찾아 제거하는 DeleteMinPath() 함수를 살펴보자.

 

void DeleteMinPath(){ //최단 경로들에 포함된 간선들을 제거
  vertex_pq = vector<priority_queue<DistInfo>>(vertex_num);  //cost와 parent의 idx저장
  pair_pq pq;
 
  pq.push({0,start_idx});
  vertex_pq[start_idx].push({0,start_idx,0});
 
  int idx, cost, next_idx, next_cost, edge_idx;
  while(!pq.empty()){
    idx = pq.top().second;
    cost = pq.top().first;
    pq.pop();
 
    if(!vertex_pq[idx].empty() && vertex_pq[idx].top().cost < cost)
      continue;
 
    for(int i=0 ; i<adj[idx].size() ; ++i){
      next_idx = adj[idx][i].to;
      next_cost = cost + adj[idx][i].cost;
      edge_idx = adj[idx][i].edge_idx;
 
      if(vertex_pq[next_idx].empty() || next_cost <= vertex_pq[next_idx].top().cost){
        if(!vertex_pq[next_idx].empty() && next_cost < vertex_pq[next_idx].top().cost)  // 정점의 pq의top보다 cost가 작은 경우만 push
        //작거나 같을때 모두 push할 경우 메모리가 초과됨. 중복을 없앤다.
          pq.push({next_cost, next_idx});
        else if(vertex_pq[next_idx].empty())  //정점의 pq가 비어있다면 push
          pq.push({next_cost, next_idx});
        vertex_pq[next_idx].push({next_cost,idx, edge_idx});
      }
 
    }
    
  }
 
  //bfs로 간선의 제거
  vector<bool> is_in_que(501,false);
  queue<int> que;
  que.push(dest_idx);
  is_in_que[dest_idx] = true;
  
  int top_cost, now_idx, top_parnet;
  while(!que.empty()){
    now_idx = que.front();
    que.pop();
 
    if(vertex_pq[now_idx].empty())
      continue;
    
    top_cost = vertex_pq[now_idx].top().cost;
 
    while(!vertex_pq[now_idx].empty() && vertex_pq[now_idx].top().cost <= top_cost){  // 간선의 pq에서 top cost와 같은 간선은 모두 제거
 
      top_parnet =  vertex_pq[now_idx].top().parent;
 
      is_delete[vertex_pq[now_idx].top().edge_idx] = true;
      vertex_pq[now_idx].pop();
 
      if(is_in_que[top_parnet]) //이미 큐에 들어있는 경우 중복을 제거하기 위해 삽입 하지 않는다.
        continue;
        
      que.push(top_parnet);
      is_in_que[top_parnet] = true;
    }
 
  }
  
}

 

일단 최단 경로들을 구하는 부분부터 생각해보자.

next_idx 정점의 pq에 최단 경로로서 간선이 저장되는 경우는

정점의 pq(vertex_pq[next_idx])의 top, 즉 next_idx 정점에 도달하는 최소 cost의 경로보다 cost가 작거나 같은 경우이다.

cost가 더 작은 경우는 top에 있던 경로는 우선순위 큐의 자동 정렬로 인해 top의 아래로 내려가게 된다.

cost가 같은 경우, 동일한 비용의 다른 경로이므로 이 또한 저장해주어야 한다.

 

이때 주의할 점이 있다.

이 문제의 오답으로는 특히 메모리 초과가 자주 등장하는데 그 이유는 다익스트라의 최적화가 진행되지 않았기 때문이다.

여러 개의 최단 경로가 저장되는 과정에서 다음과 같이 한 정점이 여러 번 다익스트라의 우선순위 큐에 삽입될 수 있다.

 

이런 경우 V와 같은 정점은 pq에 n번 지속적으로 삽입이 되고

다시 V에서 진입하는 k개의 정점이 있다고 할 때 pq에서 V가 pop이 될 때마다 k개의 정점을 pq에 다시 삽입할 수 있다.

최악의 경우 모든 V가 k개의 정점을 삽입하므로 우선순위 큐가 저장해야 하는 양이 너무 많아 메모리 초과를 발생시킨다.

따라서 이를 막기 위해 V로의 최단 cost의 경로를 이미 한번 구했다면 pq에는 V가 이미 삽입되어 있다.

cost가 같은 경로가 다시 V정점으로 접근했다면 이미 pq에 V는 삽입되었으므로 V는 더 이상 pq에 삽입할 필요가 없다.

 

단, cost가 더 작은 경로로 V에 접근했다면 V에서 뻗어 나가는 경로의 최단 경로는 다시 설정되어야 한다.

그러므로 cost가 더 작은 경우에만 다익스트라의 pq에 삽입을 해주자. (line17~ 29)

 

이제 모든 최단 경로를 각 정점의 pq에 저장했다면 목적지 정점에서부터 역순으로 간선을 거슬러 올라가면서 최단 경로를 삭제한다.

이 경우는 BFS로 구현하였는데 같은 정점이 다시 bfs의 큐 안에 삽입된다면 메모리 초과를 유발할 수 있으므로 

한 정점은 한 번만 큐에 삽입되도록 최적화를 해주자.

 

 

모든 최단 경로에 포함된 간선들을 제거해 주었다면 일반적인 다익스트라 알고리즘으로 거의 최단 경로를 구할 수 있다.

 

이와 비슷하게 각각의 정점의 pq를 이용하여 K번째 최단 경로를 구하는 문제도 풀어보자.

[백준] K번째 최단 경로 찾기(1854)

 

코드