[백준] 1647번 도시 분할 계획

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

1647번: 도시 분할 계획

전형적인 최소 신장 트리 문제였다. 문제를 읽자마자 최소 신장 트리를 구현하는데 좋은 예제라는 것을 알았다..ㅎ 하지만 조금 응용된 것이 마을 두 개를 분리하는데 길 유지비의 합의 최소값을 구하라고 하였다. 즉, 최소 신장 트리를 구한 다음에 제일 거리가 긴 곳을 없애면 된다. 하나의 길을 없애면 두 개의 마을이 생기는 거니까! 

 

parent 노드를 찾는 함수랑 노드를 합치는 함수를 이용하여 구현하였다. 이것이 코딩테스트다 10장에서 연습했던 전형적인 크루스칼 알고리즘을 사용한 후에 각각의 길을 result 벡터에 입력시켰다. 그 후에 가장 마지막( 제일 거리가 긴 곳) 을 빼주면 두 개의 분리된 마을의 길 유지비의 합이 최소가 된다!

 

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

using namespace std;

vector<pair<int, pair<int, int>>> arr;
int parent[100001];
vector<int> result;

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

void Union_node(int x, int y)
{
	x = node_parent(x);
	y = node_parent(y);
	if (x > y)
	{
		parent[x] = y;
	}
	else
	{
		parent[y] = x;
	}
}

int main()
{
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		
		//비용순으로 오름차순
		arr.push_back({ c, { a,b } });
	}
	
	for (int i = 1; i <= N; i++)
	{
		parent[i] = i;
	}

	sort(arr.begin(), arr.end());


	
	for (int i = 0; i < M; i++)
	{
		int a = node_parent(arr[i].second.first);
		int b = node_parent(arr[i].second.second);
		if (a != b)
		{
			Union_node(a, b);
			result.push_back(arr[i].first);
		}
	}

	int sum = 0;

	for (int i = 0; i < result.size() - 1; i++)
	{
		sum += result[i];
	}

	cout << sum;
}