[백준 C++] 1647 도시 분할 계획 - 최소신장트리

1647번: 도시 분할 계획

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

vector<tuple<int, int, int>> Edges;
int RootNode[100000];

int Find(int Node)
{
	if (Node == RootNode[Node])
	{
		return Node;
	}

	return RootNode[Node] = Find(RootNode[Node]);
}

void Union(int NodeA, int NodeB)
{
	int A = Find(NodeA);
	int B = Find(NodeB);

	int Min = min(A, B);
	RootNode[A] = Min;
	RootNode[B] = Min;
}

int Kruskal(int N, int M)
{
	if (N == 2)
	{
		return 0;
	}

	int Cost = 0;
	int Linked = 0;
	for (int i = 0; i < M; ++i)
	{
		int NodeA = get<1>(Edges[i]);
		int NodeB = get<2>(Edges[i]);
		if (Find(NodeA) != Find(NodeB))
		{
			Union(NodeA, NodeB);
			Cost += get<0>(Edges[i]);
			++Linked;

			if (Linked == N - 2)
			{
				break;
			}
		}
	}

	return Cost;
}

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

	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; ++i)
	{
		RootNode[i] = i;
	}

	Edges.reserve(M);
	for (int i = 0; i < M; ++i)
	{
		int A, B, C;
		cin >> A >> B >> C;
		Edges.emplace_back(C, A - 1, B - 1);
	}

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

	cout << Kruskal(N, M);
}

---

 

최소 신장 트리 & 크루스칼 알고리즘을 이용해서 푸는 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 에지 리스트로 그래프 구현 & 유니온 파인드 리스트 초기화
2. 에지 리스트를 가중치 오름차순으로 정렬
3. 가중치가 낮은 에지부터 연결 시도 - 파인드 연산을 통해 서로 다른 집합임을 판별했을 때(루트노드가 서로 다름)만 연결
4. N-2개의 에지가 연결될 때까지 단계 3 반복 -> 연결된 에지 개수 & 비용 합 카운트
5. 총 에지 비용 출력

 

주의할 점은 마을을 두 개로 분리해야하기 때문에 N-2개의 에지만 연결해야 합니다.

그리고 집이 두 개 주어졌을 때의 예외처리도 필요합니다.