[LAN] 근거리 네트워크

• 분류: 그래프, 트리
  
• 난이도: 하
• 입력: 테스트 케이스 C(<=50), 건물의 수 N(<=500), 이미 설치된 케이블의 수 M(<=2000), 0부터 N-1까지의 x좌표와 y좌표, 이미 설치된 건물의 번호 두 정수
• 출력: 모든 건물을 연결해야 할 때, 추가로 설치해야 할 케이블의 총 길이
• 소스코드

#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <iomanip> using namespace std; //상호배타적 집합 struct disjoinSet{ vector<int> parent, rank; disjoinSet(int n) : parent(n), rank(n, 1){ for (int i = 0; i < n; i++) parent[i] = i; //자기 자신을 루트, parent로 지정 } int find(int u){ if (u == parent[u]) return u; return parent[u] = find(parent[u]); } //rank가 더 큰 것을 root로 하여 합침 void merge(int u, int v){ u = find(u); v = find(v); //각자의 루트를 찾음 if (u == v) return; //같은 집합 if (rank[u] > rank[v]) swap(u, v); parent[u] = v; if (rank[u] == rank[v]) ++rank[v]; } }; const int MAX_V = 500; vector<pair<int, int> > point; //좌표 double kruskal(const int, disjoinSet&); //크루스칼 알고리즘 int main(){ int C; cin >> C; for (int i = 1; i <= C; i++){ int N, M; //건물의 수 N 이미 설치된 케이블의 수 M cin >> N >> M; point = vector<pair<int, int> >(N, make_pair(0, 0)); disjoinSet lanSet(N); for (int j = 0; j < N; j++) cin >> point[j].first; //x좌표 for (int j = 0; j < N; j++) cin >> point[j].second; //y좌표 for (int j = 0; j < M; j++){ int u, v; cin >> u >> v; lanSet.merge(u, v); } cout << fixed << kruskal(N, lanSet) << endl; } return 0; } double kruskal(const int n, disjoinSet& set){ double ret = 0.0; vector<pair<double, pair<int, int> > > edge; for (int i = 0; i < n; i++){ for (int j = i + 1; j < n; j++){ int subX = abs(point[i].first - point[j].first), subY = abs(point[i].second - point[j].second); double distance = sqrt(subX * subX + subY * subY); //root subX^2 + subY^2 edge.push_back(make_pair(distance, make_pair(i, j))); } } sort(edge.begin(), edge.end()); for (int i = 0; i < edge.size(); i++){ double cost = edge[i].first; int u = edge[i].second.first, v = edge[i].second.second; if (set.find(u) == set.find(v)) continue; //이미 같은 집합이면 set.merge(u, v); ret += cost; } return ret; } 출처: http://yejin0730.tistory.com/10 [초보개발자의 블로그]

• 소스설명: 1. disjoinSet : 상호배타적 집합 구조체. parent는 부모, rank는 깊이. find는 루트번호를 반환하며, merge는 각 집합을 합치는 함수이다.

2. kruskal(const int n, disjointSet& set): 크루스칼 최소 스패닝 트리 알고리즘을 이용. 간선의 집합을 만들어 가중치에 따라 정렬을 한다.

가장 짧은 간선을 추가하는데, 이 때 사이클이 생기지 않게 추가해야 한다. 위 구조체를 이용하여 만들 수 있다.

• 참고문제: https://algospot.com/judge/problem/read/LAN