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

그래프 이론 중 가장 대표적인 유형인 최소 신장 트리 문제

 

여기서 중요한 것만 간략히 말하자면

 

1. unordered_map으로 우선 간선과 정점 정보를 받고 vector로 변환해서 정렬하려고 하면 안됨

 

처음에는 key-value 형식으로 받은 후에 vector로 바꿔서 정렬 후에 함수 인자로 넣어서

돌리려고 했는데 이러면 문제가 발생함.

 

만약 간선의 가중치가 같으면 map 특성 때문에 계속 해당 간선 key값이 최신화됨.

 

예시를 들자면 1-2 cost = 3 이 있었는데 만약 3-5 cost = 3 이 들어오면 1-2 는 없어지고 3-5 에 대한 정보만 남는다는 거임.

그래서 그냥 vector로 다 받아주면 된다.

 

그러니까 이렇게 하면 안된다는 뜻임.

unordered_map<int, pair<int, int>> info;

//for문
info[cost] = make_pair(a,b);

이렇게 하면 map에서 각 key값은 중복될 수 없는 유일한 값이므로 계속해서 똑같은 cost에 대한 값이 들어오면 value에 있는 정점 정보 pair가 계속 최신화 된다는 뜻.

 

---

2. kruskal 로 돌리는데 이때 중요한 것은 union find를 통해 isCycle 인지만 판단해주면 된다는 것

 

작은 것부터 필요한 간선들만 선택해 적립해나가는 식이므로

해당 간선을 포함시켰을때 cycle이 되는지만 판단해주면 된다.

 

---

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

#define SIZE 10001

using namespace std;

vector<pair<int, pair<int, int>>> edges;

int V, E;
int parent[SIZE];

int findParent(int x) {
	if (parent[x] == x) return x;
	else return parent[x] = findParent(parent[x]);
}

void updateParent(int a, int b) {
	a = findParent(a);
	b = findParent(b);

	if (a != b) parent[b] = a;
}

bool isCycle(int a, int b) {
	a = findParent(a);
	b = findParent(b);

	return a == b;
}

void solve() {
	int ans = 0;
	int edgecnt = 0;

	for (int i = 0; edgecnt < V - 1; i++) {
		int cost = edges[i].first;
		int start = edges[i].second.first;
		int end = edges[i].second.second;

		if (!isCycle(start, end)) {
			ans += cost;
			updateParent(start, end);
			edgecnt++;
		}
	}

	cout << ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> V >> E;

	// union find 위해 부모 초기화
	for (int i = 0; i <= V; i++) parent[i] = i;

	int start, end, cost;
	for (int i = 0; i < E; i++) {
		cin >> start >> end >> cost;
		edges.push_back(make_pair(cost, make_pair(start, end)));
	}

	// cost 오름차순으로 정렬
	sort(edges.begin(), edges.end());
	
	solve();

	return 0;
}