[Algorithm]Baekjoon 1197 :: 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

using namespace std;
 
struct Node
{
    int node1;
    int node2;
    int weight;
};
 
 
bool cmp(const Node& a, const Node& b)
{
    return a.weight < b.weight;
}
 
int v, e, a, b, c;
int parents[10001] = { 0 };
vector<Node> edges;
 
int getParent(int node)
{
    if (node == parents[node])
    {
        return node;
    }
 
    return parents[node] = getParent(parents[node]);
}
 
bool cmpParent(int a, int b)
{
    int parentA = getParent(a);
    int parentB = getParent(b);
 
    if (parentA == parentB) return true;
    
    return false;
}
 
void unionParents(int a, int b)
{
    int parentA = getParent(a);
    int parentB = getParent(b);
 
    if (parentA < parentB)
    {
        parents[parentB] = parentA;
    }
    else
    {
        parents[parentA] = parentB;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> v >> e;
 
    for (int i = 1; i <= v; ++i)
    {
        parents[i] = i;
    }
 
    for (int i = 0; i < e; ++i)
    {
        cin >> a >> b >> c;
        edges.push_back({ a,b,c });
    }
 
    sort(edges.begin(), edges.end(), cmp);
 
    int answer = 0;
 
    for (int i = 0; i < e; ++i)
    {
        if (cmpParent(edges[i].node1, edges[i].node2) == false)
        {
            unionParents(edges[i].node1, edges[i].node2);
            answer += edges[i].weight;
            --v;
        }
 
        if (v == 1) break;
    }
 
    cout << answer;
}
 
 
 

오랜만에 연습삼아서 풀어본 MST문제이다.

크루스칼로해도되고 프림으로 해도되는데, 나는 UnionFind가 굉장히 익숙해서 크루스칼로 푸는게 편하다.

원래 MST같은문제는 오랜만에 풀면 가물가물해서 코드는 아니더라도 로직흐름은 글이라도 한번봐야되는데, 이제는 그냥 머리속에 완전히 인지된 듯 하다.(크루스칼 한정)

 

한번 더 복기할겸 적자면, 최소가중치로 그래프를 만들어야하기 때문에 가중치를 오름차순으로 정렬한다음 합집합을 만들어주면 된다. 

오름차순으로 했기때문에 현재 선택한 가중치가 여러 가중치중 가장 최저값이라는게 보장받게 되기 때문에, 간선의 양 끝 노드가 같은집합이 아니기만 하면 그냥 합쳐주면 된다. 이게 끝..

합쳐줄 때 몇개합쳤는지 검사하는것만 추가해주면 된다. (정점개수만큼 합치면 더이상 검사할필요가 없으니)