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

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 최소 신장 트리(MST) 문제로, 모든 섬을 연결하는 최소 신장 트리를 만든 후에 최소 신장 트리를 구성하는 간선 중 가장 가중치가 큰 간선을 없애면 마을을 두 개로 분할 가능하고, 두 마을의 간선의 가중치 합도 최소로 유지할 수 있다. 이 문제에서는 MST를 구하기 위해 크루스칼 알고리즘을 사용했다.

1) 사이클 테이블에 각 노드(섬)들의 부모를 자기 자신으로 지정한다.

2) 간선들의 정보를 저장하는 벡터 edges를 만들어 각 간선들의 (가중치, 노드 a, 노드 b)를 저장한다.

3) edges를 가중치의 오름차순으로 정렬한다.

4) 정렬된 벡터에 대해 크루스칼 알고리즘을 적용한다.

• 현재 순서 간선의 노드 a, 노드 b를 확인해 같은 그래프에 있지 않으면 두 노드를 이어 부모를 합치고, answer에 간선의 가중치를 누적시킨다.
• 이때 maxCost와 현재 간선의 가중치를 비교해 현재 간선의 가중치가 더 크다면 maxCost를 갱신한다.
  

5) 크루스칼 알고리즘이 종료되면 answer에는 간선들의 최소 가중치합이 저장되는데, 이 때 여기서 maxCost를 빼주면 두 개로 분할된 마을의 간선들의 최소 가중치합이 나오게 된다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <queue>

using namespace std;
typedef tuple<int, int, int> tiii;

int parent[100001];

int getParent(int n)
{
	if (parent[n] == n) return n;
	return parent[n] = getParent(parent[n]);
}

void unionParent(int a, int b)
{
	a = getParent(a);
	b = getParent(b);

	if (a < b)
		parent[b] = a;
	else
		parent[a] = b;
}

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

	return (a == b);
}

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

	int n, m;
	cin >> n >> m;
	
	for (int i = 0; i <= n; i++)
		parent[i] = i;
	
	vector<tiii> edges;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edges.push_back(tiii(c, a, b));
	}
	sort(edges.begin(), edges.end());
	
	long long answer = 0;
	int maxCost = 0;

	for (int i = 0; i < edges.size(); i++)
	{
		int curA = get<1>(edges[i]);
		int curB = get<2>(edges[i]);
		int curC = get<0>(edges[i]);

		if (!findParent(curA, curB))
		{
			unionParent(curA, curB);
			answer += curC;

			if (curC > maxCost)
				maxCost = curC;
		}
	}
	cout << answer - maxCost;
}