[백준] 1197 최소 스패닝 트리 (C++)

백준 1197 최소 스패닝 트리 문제
백준 1197 최소 스패닝 트리 소스코드

📄 문제 설명

Problem

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리란,
주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중 가중치의 합이 최소인 트리이다.

Input

첫째 줄 : 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)
다음 E개 줄 : 각 간선에 대한 정보를 나타내는 세 정수 A, B, C
(A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미)
(C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.)

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다.
가중치는 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터

Output

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

Example Input 1

3 3
1 2 1
2 3 2
1 3 3

Example Output 1

3

📝 문제 해설

이 문제는 제목처럼 최소 스패닝 트리 문제이다.

▶ 최소 신장 트리 (Minimum Spanning Tree / MST)

무향 연결 가중 그래프 G에서 간선의 가중치의 합이 최소인 신장(spanning) 트리이다.

◼ 신장 트리(spanning tree)란?
그래프 내의 모든 정점을 포함하는 트리이면서, 그래프의 최소 연결 부분 그래프이다.
최소 연결: 간선의 수가 가장 적다는 의미
(v개의 정점을 가지는 그래프의 최소 간선의 수는 (v-1)개)

◼ MST 특징
- 간선의 가중치 합이 최소
- v개의 정점을 가지는 그래프에 대해서 반드시 (v-1)개의 간선만을 이용.
- 사이클을 포함하지 않는다.

▶ MST 구현 방법 - 크루스칼 알고리즘 (Kruskal's Algorithm)

탐욕적인 방법(Greedy method)을 이용
가중치 그래프의 모든 정점을 최소 비용으로 연결하는 최적해를 구하는 것

- MST가 최소 비용의 간선으로 이루어짐
- 사이클을 포함하지 않는다
- 간선 선택을 기반한 알고리즘
- 이전 단계에서 만들어진 신장트리와 무관하게 무조건 최소 간선 선택

◼ 과정
1. 그래프의 간선을 가중치를 기준으로 오름차순 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
	- 가장 낮은 가중치 선택
	- 사이클을 형성하는 간선 제외
3. 해당 간선을 현재 MST의 집합에 추가한다.

▶ MST 구현 방법 - 프림 알고리즘 (Prim's Algorithm)

시작 정점에서부터 출발해 신장트리 집합을 단계적으로 확장시키는 방법
- 정점 선택을 기반으로 하는 알고리즘
- 이전 단계에서 만들어진 신장 트리를 확장하는 방법

◼ 과정
1. 시작 단계에서 시작정점만 MST 집합에 포함된다
2. 이전 단계에서 만들어진 MST 집합에 인접한 정점중 최소 간선으로 연결된 정점 선택
	- 인접한 간선중 가중치가 가장 낮은 간선 선택
3. 위의 과정을 (v-1)개의 간선을 가질 때까지 반복

▶ 다시 문제로 돌아와서,

MST의 두가지 알고리즘 중, 해당 문제는 Kruskal의 알고리즘으로 해결하였다.

가중치를 기준으로 오름차순 정렬을 빠르게 하기 위해 우선순위 큐를 사용했으며,
해당 간선이 사이클을 형성하는지 확인하기 위해 Union Find를 사용하였다.
(두 개의 정점의 parent가 같지 않을 때 해당 간선을 추가시키고, 같은 집합으로 합쳐준다.)

</> Source Code

#include <bits/stdc++.h>

using namespace std;

struct Edge{
	int nodeA;
	int nodeB;
	int weight;
};

struct Comp{
	bool operator()(const Edge& A, const Edge& B){
		return A.weight > B.weight;
	}
};

vector<int> parent;

int find(int node){
	if(node == parent[node]) return node;
	else return find(parent[node]);
}

void unionF(int a, int b){
	int pA = find(a);
	int pB = find(b);
	parent[pA] = pB;
}

int main() {	
	int v, e;
	scanf("%d %d", &v, &e);
	
	priority_queue<Edge, vector<Edge>, Comp> edges;
	
	int edge = 0;
	int result = 0;

	for(int i = 0; i <= v; i++){
		parent.push_back(i);
	}	
	
	for(int i = 0; i < e; i++){
		int a, b, w;
		scanf("%d %d %d", &a, &b, &w);		
		edges.push({a, b, w});
	}
	
	while(edge < v - 1 || !edges.empty()){
		Edge minE = edges.top();
		edges.pop();
		
		if(find(minE.nodeA) != find(minE.nodeB)){
			unionF(minE.nodeA, minE.nodeB);
			result += minE.weight;
			edge++;
		}
	}
	
	printf("%d", result);
	
	return 0;
}