백준1922 네트워크 연결 - C++

네트워크를 직접 연결(!!)하는 아주아주 어려운 문제이다...

모든 컴퓨터가 직간접적으로 연결되어 있어야 하고

심지어 그 비용이 가장 적어야 한다.(속도는 상관 없나보다)

 

비용이 가장 적게 모든 노드를 연결하기만 하면 되므로

최소 신장 트리(MST: Minimum Spanning Tree)를 이용하여

트리 모양으로 고리가 생기지 않도록 연결해준다.

(고리가 생기는 경우는 고리가 생기지 않는 경우보다 항상 비싸다)

 

우리는 MST 알고리즘 중 크루스칼 알고리즘(Kruskal's algorithm - Wikipedia)을 이용한다.

 

1. 가장 비용이 작은 간선부터 연결한다.(UNION FIND)

2. 같은 그룹에 속할 경우 연결하지 않는다.

간단한 그리디 알고리즘이다.

이 때 MST 가 항상 최소비용인 것은 증명되어있다.

 

간단하게, 가장 비용이 작은 간선 중 하나가 MST에 빠져있다고 가정하면,

이 간선을 추가한 후 생기는 Cycle 에서, 이 간선보다 비용이 비싼 간선을 빼면

기존 MST 보다 비용이 더 작은 MST 가 생기는 것이므로 모순이다.

#include <cstdio>
#include <queue>

using namespace std;

priority_queue<pair<int, pair<int, int>>> pq; //-비용, a, b

int parent[1002];
bool visited[1002];

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


void Union(int v, int u)
{
	v = Find(v);
	u = Find(u);
	if (v != u)
	{
		if (v < u)
			parent[u] =parent[v];
		else
			parent[v] = parent[u];

	}
}

int main()
{
	int N, M;
	int cost = 0;
	int a, b, c;
    
    scanf("%d %d", &N,&M);
    //초기화
    for (int i=0 ;i< N+1; ++i){
        parent[i] = i;
    }
    
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d %d", &a,&b,&c);
		pq.push({ -c, {a,b} }); //비용이 적은 순서대로 q에서 나온다.
		
	}
	while (!pq.empty())
	{
        int computer1 = pq.top().second.first;
        int computer2 = pq.top().second.second;
        int _cost = pq.top().first;
        //만약 부모가 같은 경우 이미 그룹에 속해있는 경우이므로 뛰어넘는다(연결하지 않는다)
		if (Find(parent[computer1]) == Find(parent[computer2]))
		{
			pq.pop();
		}//부모가 다르면 그룹끼리 연결되어 있지 않으므로 연결한다.
		else
		{
			Union(computer1, computer2);
			cost -= _cost; //음수로 QUEUE에 들어가있으므로 양수로 만들어준다.
			pq.pop();
		}
	}
    printf("%d\n", cost);
	
}