[알고리즘] 백준 1197

shininghyunho·2021년 6월 6일
0
post-thumbnail

문제

문제 링크

최소신장트리를 구하는 문제다.

신장트리는 모드 노드가 연결되어있지만 사이클을 이루지 않는 그래프다.
여기서 최소가 들어가면 연결될때 간선들의 합이 최소가 되게하는것이다.
그래서 사이클을 이루지 않으며 간선들의 합이 최소가 되게 모든 노드들을 연결하는 그래프다.

union-find

(대충 내가 설명하고싶은것만 설명)
이 문제는 union-find라는 방식으로 해결할 수 있다.
union-find는 부모를 비교해 노드들을 합치는 알고리즘이다.

  • union - 합침
  • find - 부모를 찾음

처음에 부모 배열(p)을 만들어주고 자기 자신으로 (p[i]=i) 초기화해준다.

그리고 두 노드가 이어져있다면 서로의 부모를 찾아 합친다.
1-2 연결

3-4가 연결되었다면 또 합친다.

2-3도 연결

그렇게 이어진 노드들을 계속 합치다가 모든 부모가 하나로 모여지면 모든 노드들이 연결되었다고 볼 수 있다.

이러한 union-find를 간선이 작은 순서대로 연결하면
크루스칼 알고리즘이 된다.

근데 어떤 기준으로 합친거야?

rank

단순하게 작은 인덱스를 기준으로 합치는 방법도 있고
rank 개념을 사용해 합칠수있다.

rank는 트리의 깊이와 유사한 개념이다.
(위 예제에서 1의 rank는 1이되고 2는 0일것이다.)
rank가 큰 쪽이 작은 쪽 위로가게 합칠것이다.

깊이 100의 그래프가 있고 깊이 10의 그래프가 있다고 치면
100 아래에 10을 두면 10의 말단 노드는 깊이가 11이 된다.

모든 노드들의 깊이 합을 k라고 치면 10개 노드들의 깊이가 1증가했으므로 전체 합은 k+10이 된다.

반대로 10 아래에 100을 두면 100개의 노드들이 모두 깊이가 1씩 증가해 전체 깊이의 합은 k+100이 될것이다.

손해도 이런 손해가 없다.

그래서 union할때 rank를 비교해주면 빅오를 N에서 lonN까지 줄여준다.

// rank를 비교하고 작은쪽을 큰쪽에 넣기
if (ranks[a]<ranks[b]){
    parent[a]=b;
}
else{
    parent[b]=a;
}

if (ranks[a]==ranks[b]){
    ranks[a]++;
}

경로 축소

부모를 연결하다보면 자식들이 줄줄이 소세지가 된다. 그래서 자식들의 부모를 찾을때 부모와 내 값이 같지 않으면 부모의 부모(조부모)를 찾아 내 부모로 만든다.

3이 find를 하는순간 2의 부모(1)를 부모로 만든다.

이러한 경로 축소 방법도 결국 자식이 부모를 찾을때만 축소되므로 전체 깊이를 줄일수는 없다. 그래서 rank는 꼭 써야한다.

code

/**
 * 백준 1197
 * MST
 * 최소 스패닝 트리
*/
#include <bits/stdc++.h>
using namespace std;

int v,e;
int parent[10001];
int ranks[10001]={0};
vector<pair<int,pair<int,int>>> edges;

int find(int x){
    if(parent[x]!=x){
        parent[x]=find(parent[x]);
    }
    return parent[x];
}

void unionParent(int a,int b){
    a=find(a);
    b=find(b);

    if(a==b){
        return;
    }

    // rank를 비교하고 작은쪽을 큰쪽에 넣기
    if (ranks[a]<ranks[b]){
        parent[a]=b;
    }
    else{
        parent[b]=a;
    }

    if (ranks[a]==ranks[b]){
        ranks[a]++;
    }
}

int main(void){
    cin>>v>>e;
    
    for(int i=0;i<e;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        edges.push_back({c,{a,b}});
    }
    // cost 순서로 정렬
    sort(edges.begin(),edges.end());

    // 부모 초기화
    for(int i=1;i<=v;i++){
        parent[i]=i;
    }

    int ans=0;
    int edgeNum=0;
    for(int i=0;i<edges.size();i++){
        int cost=edges[i].first;
        int a=edges[i].second.first;
        int b=edges[i].second.second;

        if(find(a)!=find(b)){
            unionParent(a,b);
            ans+=cost;
            edgeNum++;
        }
        if(edgeNum == v-1){
            break;
        }
    }
    cout<<ans<<endl;
}
profile
shining itself

0개의 댓글