[백준 C++] 1197 최소 스패닝 트리 - 최소신장트리

1197번: 최소 스패닝 트리

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> EdgeList;
vector<int> RootNode;

bool Compare(const vector<int>& Left, const vector<int>& Right)
{
‌return (Left[2] < Right[2]);
}

int Find(int Node)
{
‌if (Node != RootNode[Node])
‌{
‌‌RootNode[Node] = Find(RootNode[Node]);
‌}

‌return RootNode[Node];
}

bool Union(int NodeA, int NodeB)
{
‌int RootA = Find(NodeA);
‌int RootB = Find(NodeB);

‌if (RootA == RootB)
‌{
‌‌return false;
‌}

‌int MinRoot = min(RootA, RootB);
‌RootNode[RootA] = MinRoot;
‌RootNode[RootB] = MinRoot;

‌return true;
}

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(NULL);
‌cout.tie(NULL);

‌int V, E;
‌cin >> V >> E;

‌EdgeList.reserve(E);
‌for (int i = 0; i < E; ++i)
‌{
‌‌EdgeList.emplace_back(vector<int>(3, 0));

‌‌int Start, End, Weight;
‌‌cin >> Start >> End >> Weight;

‌‌EdgeList.back()[0] = Start - 1;
‌‌EdgeList.back()[1] = End - 1;
‌‌EdgeList.back()[2] = Weight;
‌}

‌sort(EdgeList.begin(), EdgeList.end(), Compare);

‌RootNode.reserve(V);
‌for (int i = 0; i < V; ++i)
‌{
‌‌RootNode.emplace_back(i);
‌}

‌int Sum = 0;
‌int Cnt = 0;
‌int Current = 0;
‌while (Cnt < V - 1)
‌{
‌‌int Start = EdgeList[Current][0];
‌‌int End = EdgeList[Current][1];

‌‌if (Union(Start, End))
‌‌{
‌‌‌int Weight = EdgeList[Current][2];
‌‌‌Sum += Weight;
‌‌‌++Cnt;
‌‌}

‌‌++Current;
‌}

‌cout << Sum;
}

---

크루스칼 알고리즘으로 풀었습니다.

풀이 과정은 다음과 같습니다.

 

1. 에지 리스트로 그래프 구현 & 유니온 파인드 리스트 초기화
2. 에지 리스트를 가중치 오름차순으로 정렬
3. 가중치가 낮은 에지부터 연결 시도 - 파인드 연산을 통해 서로 다른 집합임을 판별했을 때(루트노드가 서로 다름)만 연결
4. N-1개의 에지가 연결될 때까지 3번 반복 -> 연결된 에지 개수 & 비용 합 카운트
5. 총 에지 비용 출력