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

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

1647번: 도시 분할 계획

크루스칼 알고리즘을 이용하여 최소 스패닝 트리의 간선을 찾은 뒤, 최소 스패닝 트리의 간선에서 유지비가 가장 큰 간선을 없앤 나머지 길들의 유지비를 구하였다(분리된 마을 사이의 길을 없앤 것)

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
using namespace std;

int n, m;
vector<pair<int,int>> adj[100001]; //pair: 유지비, 연결정점
int parent[100001];
int rank_size[100001];

//유니온 파인드의 파인드
int find(int node)
{
	if (parent[node] == node)
		return node;

	return parent[node] = find(parent[node]);
}

//유니온 파인드의 유니온
void merge(int node1, int node2)
{
	node1 = find(node1);
	node2 = find(node2);

	if (node1 == node2)
		return;

	if (rank_size[node1] < rank_size[node2])
		parent[node1] = node2;
	
	else
	{
		parent[node2] = node1;

		if (rank_size[node1] == rank_size[node2])
			rank_size[node1]++;
	}

}

//크루스칼 알고리즘을 이용하여 최소 스패닝 트리의 간선을 찾은뒤 
//최소 스패닝 트리의 간선에서 유지비가 가장 큰 간선을 없앤 남은 길의 유지비를 구하였다
int Solve()
{
	int ret = 0;
	vector<int> selected_edge_cost;

	for (int i = 1; i <= n; i++)
		parent[i] = i;

	memset(rank_size, 0, sizeof(rank_size));

	vector<pair<int, pair<int, int>>> edge;

	for(int i=1; i<=n; i++)
		for (int j = 0; j < adj[i].size(); j++)
		{
			int u = i;
			int v = adj[i][j].second;
			int cost = adj[i][j].first;

			//그래프의 간선들을 모두 저장한다
			edge.push_back(make_pair(cost, make_pair(u, v)));
		}

	//간선을 유지비의 오름차순으로 정렬
	sort(edge.begin(), edge.end());

	//최소 스패닝 트리의 간선을 고른다
	for (int i = 0; i < edge.size(); i++)
	{
		int u = edge[i].second.first;
		int v = edge[i].second.second;

		if (find(u) != find(v))
		{
			merge(u, v);
			selected_edge_cost.push_back(edge[i].first);
		}
	}

	//최소 스패닝 트리의 간선중 유지비가 가장 큰 것은 뺀다(분리된 마을의 길을 없앤다)
	selected_edge_cost.pop_back();

	for (int i = 0; i < selected_edge_cost.size(); i++)
		ret += selected_edge_cost[i];

	return ret;
}

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

	int a, b, c;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		adj[a].push_back(make_pair(c, b));
		adj[b].push_back(make_pair(c, a));
	}

	cout << Solve();

	return 0;
}