[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을 구현하는 방향이 가장 어려웠다

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

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

#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);     } }