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

문제

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

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

입력

첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

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

풀이

문제에서 친절하게 MST를 구현하여 간선의 가중치합을 출력하라고 써있다.
크루스칼알고리즘 설명 >> https://velog.io/@cldhfleks2/Kruskal

가장먼저 가중치가 음의값과 양의 값을 가질 수 있고, 그 최대값이 int형값이므로
가중치를 long long 타입으로 입력받고 출력하도록 해야한다.

또, find, union함수를 구현해야하고 이 두가지를 이용해
사이클이 형성되는지를 체크해주면된다.
중요한점은 이 사이클이 형성되는지는 두 노드의 루트노드가 같은지를 비교하는데
이를 비교할때 find함수를 사용하도록 코딩해줘야한다.

나머지 자세한 내용은 코드에 주석처리해놨다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>
using std::vector;
typedef long long ll;

struct INFO {
	int v1, v2;
	ll w;
	bool operator < (INFO another) { //sort함수 사용을 위한 비교연산자 재정의
		return w < another.w;
	}
};

int P[10001]; //정점의 부모정점이 무엇인지 기록 
int v, e; //정점갯수, 간선갯수
vector<INFO> edge;

//현재 정점의 루트정점이 누군지 경로압축하며 찾음
int getParent(int x) {
	if (P[x] == x) return P[x];
	//현재 P[x]는 x의 부모정점. 이 부모정점의 부모를 거슬러 올라가 P[x]로 기록
	else return P[x] = getParent(P[x]); 
}

//두 정점을 하나의 집합으로(루트정점이 동일하게)
void unionParent(int x, int y) {
	x = getParent(x);
	y = getParent(y);
	if (x < y) P[y] = x; //더 작은 정점번호로 합침
	else P[x] = y;
}

//두 정점이 같은 집합인지
bool isSet(int x, int y) {
	return getParent(x) == getParent(y); //P[x] == P[y]로 하면 오류!!!
}

void init() {
	scanf("%d%d", &v, &e);
	//P배열 초기화
	for (int i = 1; i <= v; i++)
		P[i] = i;

	//연결정보 기록
	for (int _ = 0, v1, v2; _ < e; _++) {
		ll w;
		scanf("%d%d%lld", &v1, &v2, &w);
		edge.push_back({ v1, v2, w });
	}
}

int main(void) {
	init();

	sort(edge.begin(), edge.end()); //가중치로 오름차순 정렬

	ll sum = 0; //MST 가중치의 합
	for (int i = 0; i < e; i++) { //모든 간선을 확인
		int v1 = edge[i].v1;
		int v2 = edge[i].v2;
		ll w = edge[i].w;
		if (!isSet(v1, v2)) { //두 정점이 다른 집합일때(사이클이 없을때)만 MST로 추가
			sum += w;
			unionParent(v1, v2); //추가한뒤 두 정점을 하나의 집합으로 합침
		}
	}

	printf("%lld", sum);

	return 0;
}