네트워크 연결

알고리즘 구분 : 크루스칼 알고리즘

신장 트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

크루스칼 알고리즘 : 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘'이라고 하며, 그 중 가장 대표적인 알고리즘이 크루스칼 알고리즘이다.

크루스칼 알고리즘
1) 간선 데이터를 비용에 따라 오름차순으로 정렬
2) 간선을 확인해가며 현재의 간선이 사이클을 발생시키는지 확인
if 사이클이 발생하지 않는 경우 : 최소 신장 트리에 포함
else if 사이클이 발생하는 경우 : 최소 신장 트리에서 제외
3) 모든 간선에 대해 위의 과정 반복
사이클 : 간선 내에서 순환이 발생하는 것을 의미

문제 풀이 : 이 문제는 크루스칼 알고리즘으로 풀어야 하는 문제 중 가장 정석정인 문제이다.
크루스칼 알고리즘이 무엇인지 알고, 구현할 줄 알았다면 바로 풀 수 있는 문제이다. 물론, C++로 문제를 푸는 것이 너무 오랜만이였던 나머지, 정렬을 오름차순이 아닌 내림차순으로 구현하여 잘못 구현한 부분이 어디였는지 파악하는데 많은 시간을 투자했었다.

소스 코드 :

#include <bits/stdc++.h>

using namespace std;

int n, m;
int parent[1001];
vector<pair<int, pair<int, int>>> graph;
int findParent(int x);
void unionParent(int a, int b);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int a, b, cost;
		cin >> a >> b >> cost;
		graph.push_back(make_pair(cost, make_pair(a, b)));
	}
	
	for(int i = 1; i < n + 1; i++) {
		parent[i] = i;
	}
	
	sort(graph.begin(), graph.end());
	
	int result = 0;
	for(int i = 0; i < m; i++) {
		if(findParent(graph[i].second.first) != findParent(graph[i].second.second)) {
			unionParent(graph[i].second.first, graph[i].second.second);
			result += graph[i].first;	
		}
	}
	
	cout << result << endl;
	
	return 0;
}

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

void unionParent(int a, int b) {
	a = findParent(a);
	b = findParent(b);
	
	if(a < b) {
		parent[b] = a;
	}
	else {
		parent[a] = b;
	}
}

• 문제 출처 : https://www.acmicpc.net/problem/1922
• 해당 풀이는 백준에서 "맞았습니다" 판정을 받았습니다.