백준 16398 : 행성 연결

https://www.acmicpc.net/problem/16398

Kruskal 알고리즘과 UnionFind에 대한 개념을 알고있으면 쉽게 풀수 있는 문제였다.

(물론 학교 시험때는 못풀었지만..) 수업때 최소비용신장트리(MST) 개념에 대해 배웟는데

몇일만 더 빨리 배웠었으면..

아무튼 간단하게 요약하자면

MST 란 그래프의 노드를 간선으로 연결함에 있어 각 간선마다 다른 비용이 든다.

이때 그 비용을 최소화 시켜야 한다.

 1. 간선 연결은 spanning tree 구조이다.

   -> 즉 n개의 노드가 있으면 간선(edge)은 n-1개로 모든 노드를 연결 시켜야 하며

   -> 이때 n-1개로 구성한 노드는 Cycle이 돌지 않아야 한다.

MST를 풀기 위한 대표적인 알고리즘은 Kruskal 과 Prim이 있는데

이문제를 Kruskal 로 풀어보았다.

Kruskal의 기본 원리는 노드가 아닌 간선(edge)을 기준으로 생각하는 것이다.

간선(edge)가 가지고 있는 정보는 크게 3가지이다.

 1. 가중치(weight) : 실제 행성을 연결하는데 드는 비용

 2. 간선이 연결하고 있는 노드 1

 3. 간선이 연결하고 있는 노드 2

MST를 구현하기 위해서 다음 간선의 정보들을 작은 순서대로 찾는다.

이때 후보 간선을 고려할때 생각해야 할 것은

만약 이 간선을 설치했을때 Cycle이 생기냐 이다.

Cycle이 생기는 것은 이미 노드1과 노드2 서로가 다른 노드들을 통해 간접적으로 연결되어 있음에도

노드1과 노드2의 연결을 시도하기 때문이다.

따라서 Cycle을 검사할때 노드1과 노드2가 이미 간접적으로 연결되었는지의 여부를 살펴보면 된다.

이 부분은 Union find 알고리즘(disjoint set)를 사용한다.

Union-find 알고리즘은 연결된 노드들의 부모노드를 지정해주는 것이다.

각 노드를 연결할때는 각 노드의 최종 부모끼리 부모관계를 만들어준다.

해당 노드가 연결된 뿌리노드가 다르 후보노드의 뿌리노드와 달라야 한다.

뿌리노드가 같으면 이미 연결되어 있다는 이야기임.

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

#include <iostream> #include <vector> #include <algorithm> using namespace std; class edge; int n; vector<edge> v; int parent[1001] = {0, }; int cost = 0; class edge{ public: int i, j, w; edge(int i = 0, int j = 0, int w = 0) :i(i),j(j),w(w){} bool operator<(const edge &e) const{ return (w < e.w); } }; //재귀호출을 이용한 v노드의 root노드 찾기 int findroot(int v){ if(parent[v] == v){ return v; } //재귀의 비효율적인 연산을 막기 위해 //Memoization 사용 return parent[v] = findroot(parent[v]); } void kruskal(){ sort(v.begin(), v.end()); //root 설정. for(int i = 1; i <= n; i++){ parent[i] = i; } for(auto it = v.begin(); it != v.end(); it++){ //모든 v의 edge를 돌면서 해당 간선이 //cycle이 도는지 확인 int curw = it->w; int rooti = findroot(it->i); int rootj = findroot(it->j); if(rooti != rootj){ //조상이 같지 않음--> cycle이 존재안함 //union해도됨 //현재 연결된 노드의 뿌리노드의 부모를 //다른 노드의 뿌리노드로 설정해서 부모관계를 형성한다 parent[rootj] = rooti; cost += curw; } } } int main(){ cin >> n; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ int weight; cin >> weight; if(i < j){ v.push_back(edge(i, j, weight)); } } } kruskal(); cout << cost << endl; return 0; }