[알고스팟] LAN - 근거리 네트워크 (C++, 프림 MST)

문제

 

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

algospot.com :: LAN

 

풀이

 

종만북 난이도: 하

 

모든 건물들이 같은 컴포넌트에 속하도록 새로 연결하는 간선들의 최솟값을 구하는 문제이므로 최소 스패닝 트리(Minimum Spanning Tree) 문제이다.

 

 

최소 스패닝 트리를 해결하기 위한 알고리즘은 대표적으로 두 가지가 존재한다.

 

 

1. 크루스칼(Kruskal) 최소 스패닝 트리 알고리즘

 

크루스칼 알고리즘은 모든 간선을 저장한 후 정렬하여 가장 작은 가중치의 간선을 차례대로 추가(스패닝) 시킨다.

따라서 간선의 개수 E에 지배적인 알고리즘이다.

이때 정점들이 사이클을 이루지 않도록, 추가하는 간선(u, v)의 컴포넌트를 Union-Find(분리 집합) 알고리즘으로 확인한다.

 

 

2. 프림(Prim) 최소 스패닝 트리 알고리즘

 

트리에서 해당 정점까지의 최단 간선을 저장하는 배열 min_weight[V]이용하여 구현한다.

min_weight에서 가장 작은 간선을 새로 추가하고 추가된 정점을 통해 min_weight[]를 갱신할 수 있다면 갱신한다.

간선은 새로 추가된 정점의 인접 간선만 검사하므로, 모든 간선은 단 한번만 검사 된다.

따라서 거의 모든 정점끼리 연결된 밀집 그래프에서는

모든 간선을 저장해 정렬하는 크루스칼 알고리즘에 비해 빠르게 동작한다.

 

 

 

다시 이번 문제로 돌아와서 그래프를 생성해보자.

문제에서 이미 케이블이 연결된 건물은 스패닝 트리에서 이미 연결되어 같은 컴포넌트를 이루는 정점들과 같다.

따라서 최소 스패닝 트리를 계산 시, 이미 연결된 간선의 가중치가 계산되지 않도록 이 간선들은 가중치를 0으로 저장해 주자.

 

문제는 다른 간선들인데, 모든 건물들은 다른 모든 건물들과 연결될 수 있으므로 모든 정점끼리 연결된 그래프를 생성해주어야 한다.

따라서 크루스칼 알고리즘 보다는 프림 알고리즘을 사용하는 것이 빠를 수 있다.

중복되는 계산을 피하며, u와 v정점 사이의 간선을 위치 좌표를 계산하여 dist[u][v]에 저장해 주자.

 

dist = vector<vector<double>>(building_num, vector<double>(building_num,-1));
int u, v, x_cap, y_cap;
double len;
 
for(int i =0 ; i<cable_num ; ++i){
  scanf("%d %d", &u, &v);
  //이미 연결된 간선은 추가 비용에 계산되지 않는다.
  dist[u][v] = dist[v][u] = 0;
}
 
for(int i=0; i<building_num ; ++i)
  for(int j=0; j<building_num ; ++j)
    //거리가 계산되지 않은 정점들 간의 거리를 추가해주자.
    if(dist[i][j] == -1){
      x_cap = abs(buildings_pos[i].first - buildings_pos[j].first);
      y_cap = abs(buildings_pos[i].second - buildings_pos[j].second);
      len = pow(x_cap, 2) + pow(y_cap,2);
      len = sqrt(len);
      dist[i][j] = dist[i][j] = len;
    }

 

 

 

이제 그래프를 모두 생성하였으므로 프림 알고리즘으로 최소 스패닝 트리의 가중치를 계산해 주자.

 

double Prim(){
  vector<bool> added(building_num,false);
  vector<double> min_weight(building_num, INF);
  double min_spanning = 0;
 
  //시작은 정점 0부터
  min_weight[0] =0; 
  for(int iter = 0; iter<building_num ; ++iter){
    int u = -1; //다음에 트리에 추가될 정점 u
 
    for(int v = 0; v<building_num ; ++v)
      //현재 저장된 min_weight중에 가장 작은 정점으로
      if(!added[v] && (u == -1 || min_weight[u] > min_weight[v]))
        u = v;
    
    //스패닝 트리에 추가
    min_spanning += min_weight[u];
    added[u] = true;
 
    double weight;
    for(int v=0; v<building_num ; ++v){
      if(added[v])  //이미 스패닝 트리에 추가된 정점은 패스
        continue;
 
      weight = dist[u][v];
      //현재 min_weight보다 더 작은 경우만 갱신해줌
      if( min_weight[v] > weight)
        min_weight[v] = weight;
    }
 
  }
  return min_spanning;
}

 

 

코드