[백준] 14950번 : 정복자

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 최소 신장 트리(MST) 문제로, 모든 노드(== 도시)에서 다른 모든 노드로 향하는 간선이 있다고 가정하고, 이 간선들에 대해 크루스칼 알고리즘을 사용하여 모든 노드들이 이어지되, 이어지는 간선들의 가중치의 합이 최소가 되는 경우를 구해야 한다. 단, 도시가 하나 이어질 때마다 가중치가 증가하는 부분을 고려해야 한다.

1) 모든 노드들 사이에 존재하는 간선에 대한 tuple(두 노드 간 가중치, 노드A 번호, 노드B 번호)들을 저장하는 벡터인 edges에 모든 노드에서 다른 모든 노드로 향하는 간선에 대한 가중치를 계산해 저장한다.

2) edges 벡터에 대해 크루스칼 알고리즘을 적용한다.

• edges 벡터를 가중치의 오름차순으로 정렬한다.
• 모든 노드들에 대한 사이클 테이블이 자기 자신을 가리키도록 한다.
• 간선들을 차례대로 확인하며 아래 과정을 반복한다.
  • 간선에 연결된 노드A와 노드B가 같은 부모를 갖는지(같은 그래프에 포함되는지) 확인한다. (== find)
  • 만약 같은 부모를 갖지 않는다면 두 노드의 부모를 같게 합친다. (== union)
  • sum에 해당 간선의 가중치 + (t * count)를 누적한다.
    • sum : mst를 이루는 모든 간선의 가중치의 합
    • count : 지금까지 정복한 도시의 개수
    • 도시가 하나 정복될 때마다 다른 도시의 비용이 t만큼 증가하기 때문에, 다음 도시를 정복할 때 (지금까지 정복된 도시의 개수 * t)만큼 더 더해주어야 한다.
  • count를 하나 증가시킨다.

3) 위 크루스칼 알고리즘 과정이 끝나면 sum에 모든 도시를 정복하는 데에 필요한 최소 비용이 저장된다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
typedef tuple<int, int, int> tiii;

int n, m, t;
vector<tiii> edges;
int parent[10001];

int getParent(int n)
{
	if (parent[n] == n)
		return n;
	else
		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(nullptr); cout.tie(nullptr);

	cin >> n >> m >> t;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edges.push_back(tiii(c, a, b));
		edges.push_back(tiii(c, b, a));
	}

	sort(edges.begin(), edges.end());
	for (int i = 1; i <= n; i++)
		parent[i] = i;
	
	int sum = 0;
	int count = 0;
	for (int i = 0; i < edges.size(); i++)
	{
		int curA = get<1>(edges[i]);
		int curB = get<2>(edges[i]);

		if (!findParent(curA, curB))
		{
			unionParent(curA, curB);
			sum += get<0>(edges[i]);
			sum += t * count;
			count++;
		}
	}
	cout << sum;
}