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

1. 문제

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

1647번: 도시 분할 계획

 

2. 알고리즘 분류

• 그래프 이론
• 최소 스패팅트리

 

3. 소스 코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, M, ans, max_cost;
int parent[100005];
vector<pair<int, pair<int,int>>> edges;

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

void Union(int a, int b)
{
	int Pa = Find(a);
	int Pb = Find(b);

	if (Pa != Pb) parent[Pb] = Pa;
}

vector<pair<int, pair<int, int>>> kruskal()
{
	vector<pair<int, pair<int, int>>> mst;

	// 각 간선 정보 탐색
	for (int i = 0; i < edges.size(); i++)
	{
		pair<int, pair<int, int>> cur_edge = edges[i];

		int start = cur_edge.second.first;
		int end = cur_edge.second.second;
		int cost = cur_edge.first;

		// 사이클 여부 확인하여, 사이클이 발생하면 해당 정보는 넘어가기
		if (Find(start) == Find(end)) continue;

		// 사이클이 발생하지 않았다면 해당 간선 정보를 추가
		mst.push_back(cur_edge);
		ans += cost;
		max_cost = max(max_cost, cost);

		Union(start, end);
		
		// 최소 스패닝 거리가 노드의 개수 - 1이라면(다 찾았다면..) 함수 끝내기
		if (mst.size() == N - 1) return mst;
	}

	return mst;
}

int main() 
{
	// N : 집의 개수, M : 길의 개수 입력
	scanf("%d %d", &N, &M);

	// 길의 정보 입력
	for (int i = 0; i < M; i++)
	{
		int A, B, C;

		scanf("%d %d %d", &A, &B, &C);

		edges.push_back({ C, {A, B} });	
	}

	// 길의 정보들을 비용 기준으로 오름차순 정렬
	sort(edges.begin(), edges.end());

	// parent 초기화
	for (int i = 1; i <= N; i++)
		parent[i] = i;

	// 최소 스패닝 트리 구하기
	vector<pair<int, pair<int, int>>> mst = kruskal();

	// 2개의 마을로 분리하기 위해, 구한 최소 스패닝 트리에서 최대 거리를 빼기
	ans -= max_cost;

	// 정답 출력
	printf("%d", ans);

	return 0;
}

 

4. 유용한 문법과 알고리즘

 1) Union-Find 알고리즘

• 각 노드들을 중복되지 않게 집합으로 묶어주는 알고리즘

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

void Union(int a, int b)
{
	int Pa = Find(a);
	int Pb = Find(b);

	if (Pa != Pb) parent[Pb] = Pa;
}

 

 2) Kruskal 알고리즘

• 최소 스패닝 트리(최소 비용으로 각 노드들을 연결하는 트리)를 구하는 알고리즘

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

void Union(int a, int b)
{
	int Pa = Find(a);
	int Pb = Find(b);

	if (Pa != Pb) parent[Pb] = Pa;
}

vector<pair<int, pair<int, int>>> kruskal()
{
	vector<pair<int, pair<int, int>>> mst;

	// 각 간선 정보 탐색
	for (int i = 0; i < edges.size(); i++)
	{
		pair<int, pair<int, int>> cur_edge = edges[i];

		int start = cur_edge.second.first;
		int end = cur_edge.second.second;
		int cost = cur_edge.first;

		// 사이클 여부 확인하여, 사이클이 발생하면 해당 정보는 넘어가기
		if (Find(start) == Find(end)) continue;

		// 사이클이 발생하지 않았다면 해당 간선 정보를 추가
		mst.push_back(cur_edge);
		ans += cost;
		max_cost = max(max_cost, cost);

		Union(start, end);
		
		// 최소 스패닝 거리가 노드의 개수 - 1이라면(다 찾았다면..) 함수 끝내기
		if (mst.size() == N - 1) return mst;
	}

	return mst;
}