[Inflearn] 원더랜드(Kruskal MST 알고리즘 : Union&Find 활용)(c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고, 나머지 도로는 폐쇄

     - 재정에 도움이 되는 도로는 비용을 음수로 표현

     - 모든 도시를 연결하면서 드는 최소비용을 출력

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

우선 이 문제를 풀기 전에 Kruskal 알고리즘이 무엇인지 알아야 할것 같다.

Greedy한 방법으로 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하여 

최적 해답을 구하는 것이다.

MST(최소 비용 신장 틀)가 최소 비용의 간선으로 구성되고, 사이클을 포함하지 않는 조건에 근거하여

각 단계에서 사이클을 이루지 않는 최소 비용 간선을 택해야 한다.

Kruskal 알고리즘을 구현하기 위해

1. 그래프 간선들을 가중치의 오름차순으로 정렬

2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택

  - 가장 낮은 가중치를 먼저 선택

  - 사이클을 형성하는 간선을 제외

3. 선택된 간선을 MST 집합에 추가

먼저 그래프 간선들을 가중치의 오름차순으로 정렬해보자.

1 2	1 9	2 3	2 8	2 9	3 4	3 7	4 5	5 6	5 7	7 8	8 9
12	25	10	17	8	18	55	44	60	38	35	15

간선들의 가중치를 오름차순으로 정렬하기 위해 

두 정점과 가중치 정보를 담는 구조체를 만들어서 정렬하였다.

2 9	2 3	1 2	8 9	2 8	3 4	1 9	7 8	5 7	4 5	3 7	5 6
8	10	12	15	17	18	25	35	38	44	55	60

다음으로 순서대로 사이클을 형성하지 않는 간선을 선택한다.

사이클을 형성하지 않는 간선은 MST에 저장한다.

사이클이 형성되는지 확인하기 위해 Union&Find 알고리즘이 활용된다.

초기 unf 는 단독 집합으로 부모 노드가 자기 자신으로 초기화된다.

unf[]

1	2	3	4	5	6	7	8	9
1	2	3	4	5	6	7	8	9

이제 작은 가중치를 가진 간선부터 선택해보자.

먼저 2 9 : 8,

2의 부모 노드는 9가 되고 cost = 8

unf[]

1	2	3	4	5	6	7	8	9
1	9	3	4	5	6	7	8	9

다음 2 3 : 10,

9의 부모 노드는 3이 되고 cost = 18

unf[]

1	2	3	4	5	6	7	8	9
1	9	3	4	5	6	7	8	3

다음 1 2 : 12,

1의 부모 노드는 3이 되고 cost = 30

unf[]

1	2	3	4	5	6	7	8	9
3	3	3	4	5	6	7	8	3

다음 8 9 : 15,

8의 부모 노드는 3이 되고 cost = 45

unf[]

1	2	3	4	5	6	7	8	9
3	3	3	4	5	6	7	3	3

다음 2 8 : 17,

2와 8의 부모 노드가 같으므로 사이클이 형성된다. 

이럴 경우 pass

unf[]

1	2	3	4	5	6	7	8	9
3	3	3	4	5	6	7	3	3

...

이와 같은 과정으로 진행하면 될것이다.

#. Code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int v, cost = 0, parent[101];
 
struct info
{
    int s;
    int e;
    int w;
    info(int a, int b, int c)
    {
        s = a;
        e = b;
        w = c;
    }
    bool operator<(const info &d) const
    {
        return w < d.w;
    }
};
 
int Find(int v)
{
    if (parent[v] == v)
        return v;
    else
        return parent[v] = Find(parent[v]);
}
 
void Union(info& info)
{
    info.s = Find(info.s);
    info.e = Find(info.e);
 
    if (info.s != info.e)
    {
        parent[info.s] = info.e;
 
        cost += info.w;
    }
}
 
void Set()
{
    int i = 0;
    for (i = 1; i <= v; i++)
        parent[i] = i;
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int e, i, a, b, c;
    vector<info> vt;
 
    scanf("%d %d", &v, &e);
    Set();
    for (i = 0; i < e; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
 
        vt.push_back(info(a, b, c));
    }
 
    sort(vt.begin(), vt.end());
 
    for (i = 0; i < e; i++)
        Union(vt[i]);
 
    printf("%d\n", cost);
 
    return 0;
}

음.. 코드가 길어졌다..

우선 구조체 부분은 여기를 참고

Union&Find 부분은 여기를 참고하면 된다.

line 9~24) 구조체에서는 start, end 정점과 간선의 가중치를 저장하고 있다.

        이번에는 생성자와 operator 를 구조체 안에 잘 생성하였다 하핳 저번에는.. 아주 ...

   operator 는 sort 과정에서 사용하고 가중치 기준 오름차순으로 정렬할 것이다.

line 26~45) 이 부분은 Union & Find 기초? 문제를 참고하면 더 쉽게 이해할 수 있을 것이다.

          그 예제와 동일하게 구현하였다. 다만 line 43 이 추가된 차이? 

          부모노드가 다를 경우 가중치를 더해주는 과정이다.

가중치를 연산하는 과정을 제외하고는 Union & Find 기본 예제와 다를게 없다.

구조체를 만들고 가중치기준으로 정렬하는 차이 정도?!

#. Other code

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
 
int unf[10001];
 
struct Edge{
    int s;
    int e;
    int val;
    Edge(int a, int b, int c){
        s=a;
        e=b;
        val=c;
    }
    bool operator<(const Edge &b)const{
        return val<b.val;
    }
};
 
int Find(int v){
    if(v==unf[v]) return v;
    else return unf[v]=Find(unf[v]);
}
 
void Union(int a, int b){
    a=Find(a);
    b=Find(b);
    if(a!=b) unf[a]=b;
}
 
int main(){
    vector<Edge> Ed;
    int i, n, m, a, b, c, cnt=0, res=0;
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++){
        unf[i]=i;
    }
 
    for(i=1; i<=m; i++){
        scanf("%d %d %d", &a, &b, &c);
        Ed.push_back(Edge(a, b, c));    
    }
 
    sort(Ed.begin(), Ed.end());
    for(i=0; i<m; i++){
        int fa=Find(Ed[i].s);
        int fb=Find(Ed[i].e);
        if(fa!=fb){
            res+=Ed[i].val;
            Union(Ed[i].s, Ed[i].e);
        }
    }
    printf("%d\n", res);
 
    return 0;
}

강사님은 부모노드가 다를 경우 Union 하도록 구현하여서

더 효율적인 코드가 되었다. 나는 무조건 Union 시켰는데..

이렇게 하나하나 배워가는거지!

line 9~21) 구조체는 강사님과 거의 동일하게 만든것 같다. (사실 전에 비슷하게 구현한 문제가 있어서 배워둔 것이지만..)

line 24~32) Union&Find 도 이전 문제와 동일하다.

line 38~40) Union&Find 를 위해 단독 집합을 만든다.

line 42~45) 구조체를 담는 vector에 입력 정보를 저장한다.

line 47) Kruskal 알고리즘의 첫 번째 단계인 그래프 간선들을 가중치의 오름차순으로 정렬하는 단계이다.

line 48~55) Kruskal 알고리즘의 두 번째 단계인 

    정렬된 간선 리스트에 순서대로 사이클을 형성하지 않는 간선을 선택하는 단계이다.

    먼저 line 49~51 에서 두 정점의 부모 노드가 같은지 확인한 후 다르다면!

    가중치를 더해주고 line 53 에서 집합화를 시켜준다.

    내 코드는 먼저 집합을 시켜주고 부모 노드가 같은지 확인하느라 구조체를 함수에 넘겨주면서

    비용이 더 늘어났을 것이다..

    조금 더 간결하게 최적화하며 구현하는 연습이 필요하다.

#. Result

  - Input --------------------------------------------------------

9 12 

1 2 12 

1 9 25 

2 3 10 

2 8 17 

2 9 8 

3 4 18 

3 7 55 

4 5 44 

5 6 60 

5 7 38 

7 8 35 

8 9 1

------------------------------------------------------------------

  - Output --------------------------------------------------------

196

------------------------------------------------------------------