[C++] 1197번 최소 스패닝 트리 - 최소 스패닝 트리, Union-Find

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

#define MAX_VERTEX 10001
#define MAX_TRUNK 100001

using namespace std;
typedef long long int lld;

int V, E;  //정점의 개수 V, 간선의 개수 E
vector<tuple<int, int, int>> map[MAX_TRUNK];  //정점의 연결관계 표시 맵
int root[MAX_VERTEX];  //union-find 용
lld w;  //가중치의 합

int find(int x)  //x의 루트 찾기
{
    if(root[x]==x)
        return x;
    else
        return root[x]=find(root[x]);
}

void _union(int x, int y)
{
    x=find(x); y=find(y);
    
    if(x==y)
        return;
    
    root[y]=x;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int cnt=0;  //추가한 간선의 개수
    
    cin >> V >> E;
    
    for(int i=0; i<E; i++) {
        int A, B, C;  //A->B 가중치 C
        
        cin >> A >> B >> C;
        map[i].push_back({C, A, B});
    }
    
    sort(map, map+E);  //간선의 가중치를 오름차순으로 정렬
    
    for(int i=1; i<=V && cnt<V-1; i++)  //union-find를 위한 초기화
        root[i]=i;
    for(int i=0; i<E; i++) {  //최소 스패닝 트리는 n-1개의 간선으로 연결되어 있음
        int u = get<1>(map[i].front());  //연결하는 두 정점 불러오기
        int v = get<2>(map[i].front());
        
        if(find(u) == find(v))  //순환 회로를 구성할 경우 pass
            continue;
        _union(u, v); cnt++;
        w+=get<0>(map[i].front());  //가중치 추가하기
    }
    cout << w;
    
    return 0;
}

 

 

엄.. 최소 스패닝 트리랑 Union Find알고리즘은 처음 보는 알고리즘이라서 맨 처음 공부할 때 약간 어버버 거리기는 했지만 그래도 나름대로 간단한 알고리즘들인 것 같다.

 

솔직히 이해가 잘되지만 문제에 쓰기 어려운 DP가 더 공부하기 어려운 알고리즘이 아닐까...? 아무튼 Kruskal 알고리즘이 왜 최적 사이클을 말해주는지는 이해 못했지만... 뭐 플래 달고 나서 이해하면 되겠지.. 글치 않을까?

 

참고한 사이트는 아래에 있다. 아 참고로 나는 54ms가 나왔는데 아마도 union find 최적화를 안 해서 그런 것 같다. rank에 따라 누구를 위에 넣을 지를 해줘야 하는데... 뭐 그건 그때가서 고치면 되겠지!

 

<Kruskal 알고리즘>

https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

[알고리즘] Kruskal 알고리즘 이란 - Heee's Development Blog

 

<Union-Find 알고리즘>

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

 

<C++ 튜플 사용법>

https://ldgeao99.tistory.com/343

(23) C++ tuple헤더의 tuple 사용법

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.