[알고스팟] TPATH - 여행 경로 정하기 (C++, 크루스칼 MST)

문제

 

https://algospot.com/judge/problem/read/TPATH

algospot.com :: TPATH

 

풀이

 

종만북 난이도: 상

 

 

최소 스패닝 트리(MST, Minimum Spanning Tree)을 잘 응용해야 풀 수 있는 문제.

 

MST 문제임에도 0번 도시에서 N-1번 도시까지의 경로 중 속도 차이의 최솟값을 묻고 있다.

최단 경로와는 다르게 경로들 중에서 최대 속도와 최소 속도의 차가 최소가 될 수 있게 만드는 길을 찾고 있다.

 

이런 문제에서 MST를 어떻게 이용해야 할까?

답은 상한과 하한을 이용하는 것이다.

하지만 상한과 하한의 쌍을 일일이 선택하여 계산해 주는 것은 너무 많은 계산이 필요하다.

 

그 해결법은 크루스칼 MST 알고리즘의 원리 있다.

크루스칼 알고리즘은 모든 간선을 cost 순으로 정렬하여 작은 cost의 간선으로 트리를 스패닝시켜 MST를 구한다.

따라서 간선이 정렬된 순서대로 앞에서부터 차례대로 MST 하한(Lower Bound, 트리의 간선으로 포함될 수 있는 최솟값)으로 설정하여,  해당 하한 이상의 간선만을 포함하는 MST를 구하면 된다.

 

이때 시간 복잡도가 걱정이 될 수 있는데 크루스칼 알고리즘에서 정렬한 간선의 정보를 그대로 계속 사용할 수 있고

구현한 분리 집합(Union-Find) 자료구조는 상수 시간의 속도를 가지므로 전체 시간 복잡도는 O(E^2)이다.

(간선의 정렬(초기에 한 번만) = E logE , 모든 하한 시도(E) x 크루스칼 MST(E) = E*E)

=> O( E logE + E^2) = O(E^2)

 

class DisjointSet{  // Union find 구현
  public:
  vector<int> parent, rank;
 
  DisjointSet(int n): parent(n), rank(n){
    for(int i=0; i<parent.size() ; ++i) //초기는 자신이 루트
      parent[i] = i;
  }
 
  int Find(int u){
    if(parent[u] == u)
      return u;
    return parent[u] = Find(parent[u]);
  }
 
  void Union(int u, int v){
    u = Find(u); v = Find(v);
    if(u == v)
      return;
 
    if(rank[v] < rank[u]) //rank는 항상 v가 크게 유지
      swap(u,v);  
 
    parent[u] = v;  //u를 v의 하위로 Union
    if(rank[u] == rank[v])
      rank[v]++;
 
    return;
  }
};

 

 

이때 중요한 점은 MST가 모든 정점을 포함할 필요가 없다는 것이다.

우리가 구하고 싶은 것은 0번 역에서 N-1번 역까지의 최소 속도 차이다.

따라서 시작 정점과 목적 정점까지의 경로만 스패닝 트리에 포함되면 답을 구할 수 있다.

 

그러므로 크루스칼 알고리즘을 진행하며 Union-Find 알고리즘을 통해 0번 역에서 N-1번 역이 연결된 시점의 간선이

해당 하한에서 가장 큰 cost를 가지는 간선이므로 MST의 상한(Upper Bound)가 된다.

 

int KruskalMinUpper(vector<LineInfo>& edges , const int lower_idx){
  DisjointSet sets(station_num);
 
  int u, v, union_cnt =0;
  //lower_idx부터 시작
  for(int i=lower_idx; i<edges.size() ; ++i){
    u = edges[i].u; v = edges[i].v;
 
    if(sets.Find(u) == sets.Find(v))
      continue;
    
    sets.Union(u, v);
    union_cnt++;
//시작과 끝점의 연결성 확인
    if(sets.Find(0) == sets.Find(station_num-1))
      return edges[i].speed;
 
     //모든 정점이 연결되었으므로 for문 탈출
    if(union_cnt == station_num-1)  
      break;
  }
  return 1001;
}

 

 

이제 간선의 순서대로 하한을 늘려가면서 MST의 상한과의 차이를 계산해주자.

 

 

 

 

코드