[백준/BOJ] 백준 1185번 : 유럽여행

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

1185번: 유럽여행

n-1개의 길만 남겨야 하고, 시작 지점으로 다시 돌아와야 되기 때문에 최소 스패닝 트리 형식으로 생각을 하고, 시작 지점은 방문할 때 드는 비용이 가장 작은 지점으로 하였고, 한번 간 길은 무조건 다시 그 길로 돌아와야 된다고 생각하고 문제를 해결했다.

 

코드

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

int n, p;
vector<pair<int, pair<int, int>>> edge;
int node_cost[10001];
int parent[10001];
int height[10001];
int start_cost = 987654321;

void Pre()
{
	for (int i = 1; i <= 10000; i++)
	{
		parent[i] = i;
		height[i] = 0;
	}
}

//유니온 파인드의 파인드
int Find(int node)
{
	if (node == parent[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 (height[node1] < height[node2])
		parent[node1] = node2;

	else
	{
		parent[node2] = node1;

		if (height[node1] == height[node2])
		{
			height[node1]++;
		}
	}

}

//크루스칼 알고리즘을 이용한다
int Solve()
{
	Pre();

	int ret = 0;

	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;
		int cost = edge[i].first;

		if (Find(u) != Find(v))
		{
			Merge(u, v);
			ret += cost;
		}
	}

	ret += start_cost;

	return ret;
}

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

	int c;
	int s, e, l;

	cin >> n >> p;

	for (int i = 1; i <= n; i++)
	{
		cin >> c;
		node_cost[i] = c;

		//시작 지점은 방문할때 드는 비용이 가장 작은 지점으로 한다
		start_cost = min(start_cost, c);
	}

	for (int i = 0; i < p; i++)
	{
		cin >> s >> e >> l;

		//n-1개의 길만 있으므로 최소 스패닝 트리의 형식으로 한번 그길을 가면 다시 그 길로 돌아와야 하므로
		//edge의 가중치를 l * 2 + node_cost[s] + node_cost[e]로 하였다
		edge.push_back(make_pair(l * 2 + node_cost[s] + node_cost[e], make_pair(s, e)));
	}

	cout << Solve();

	return 0;
}