[ALGOSPOT] LAN 근거리 네트워크

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

최소 신장 트리(Minimum Spanning Tree)를 이용하는 문제

<최소 신장 트리 종류>

1. Kruskal algorithm

 1.1 간선의 가중치를 작은 순으로 나열

 1.2 나열한 간선 순서대로 연결해 본후 cycle이 생기면 연결하지 않음

 1.3 위의 과정 반복

2. Prim algorithm

참고 : http://www.playsw.or.kr/repo/cast/106

참고 : http://blog.naver.com/PostView.nhn?blogId=cky5122&logNo=80174535762&parentCategoryNo=162&categoryNo=206&viewDate=&isShowPopularPosts=false&from=postView

<algorithm>

이 문제에서는 1번 Kruska 알고리즘을 사용했다. 

1. 간선의 가중치를 priority queue를 이용하여 작은 순으로 나열

+)

priority_queue<int> max_heap; //이 우선순위 큐는 큰 수가 맨 처음으로

priority_queue<int,vector<int>,greater<int>> min_heap; //이 우선순위 큐는 작은 수가 처음으로

 + greater -> #include <functional>

 + priority_queue -> #include <queue>

 + vector -> #include <vector>

2. parent라는 배열을 두어 자신의 최상위 부모를 저장

 -> 초기는 자기 자신이 최상위 부모이므로 자신의 값을 저장

3. 미리 연결된 노드 좌표를 입력 받은 후 parent를 갱신

4. 간선의 가중치가 작은 수부터 연결 -> 최상위 부모가 같으면 연결하지 않음 (cycle이 존재)

+)

cycle을 구현하는 방향이 가장 어려웠다

처음에는 인접 배열을 이용했으나 너무 복잡해서 구글링을 참고하여 구현하였다

아직 그래프 공부가 많이 부족하다

#include <iostream> #include <queue> #include <vector> #include <fstream> #include <algorithm> #include <functional> using namespace std; #define ABSOLUTE(X,Y) (X-Y)<0?(Y-X):(X-Y) #define PAIR pair<double,pair<int,int>> int Node_Count, Selected_Node_Count; vector<int>parent; vector<pair<int, int>>coordinate; double Distance(int index1, int index2) { return sqrt(pow(ABSOLUTE(coordinate[index1].first, coordinate[index2].first), 2) + pow(ABSOLUTE(coordinate[index1].second, coordinate[index2].second), 2)); } int Find(int index) { if (index == parent[index]) { return index; } else { return parent[index] = Find(parent[index]); } } void Union(int index1, int index2) { index1 = Find(index1); index2 = Find(index2); if (index1 == index2) { return; } parent[index1] = index2; } int main() { int For_Count; cin >> For_Count; while (For_Count--) { cin >> Node_Count >> Selected_Node_Count; double Result = 0; parent = vector<int>(Node_Count); coordinate = vector<pair<int, int>>(Node_Count); priority_queue <PAIR, vector<PAIR>, greater<PAIR>> node_distance; for (int j = 0; j < Node_Count; j++) { parent[j] = j; cin >> coordinate[j].first; } for (int j = 0; j < Node_Count; j++) { cin >> coordinate[j].second; } for (int j = 0; j < Selected_Node_Count; j++) { int index1, index2; cin >> index1 >> index2; int Find_index1 = Find(index1); int Find_index2 = Find(index2); if (Find_index1 != Find_index2) { Union(index1, index2); } } for (int j = 0; j < Node_Count; j++) { for (int k = j + 1; k < Node_Count; k++) { node_distance.push(make_pair(Distance(j, k), make_pair(j, k))); } } while (!node_distance.empty()) { double distance = node_distance.top().first; int index1 = node_distance.top().second.first; int index2 = node_distance.top().second.second; node_distance.pop(); int Find_index1 = Find(index1); int Find_index2 = Find(index2); if (Find_index1 != Find_index2) { Union(index1, index2); Result += distance; } } printf("%0.10f\n", Result); } }