[백준] 21924번 : 도시 건설

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 최소 신장 트리(MST) 문제로, 주어진 모든 도로를 이을 때의 가중치 합에서 MST의 가중치 합(== 최소 가중치 합)을 빼면 금액이 얼마나 절약되는지 구할 수 있다. 다만 MST를 구할 수 없는 경우에는 -1을 출력해야하므로, 어떤 경우에 MST가 성립하지 않는지 조건을 찾아야 한다. 이 문제에서는 MST를 구하기 위해 프림 알고리즘을 사용했다.

1) 각 노드에 대해 연결되어 있는 다른 노드들의 번호와 가중치를 입력 받아 저장하는 edges를 만들어 각 노드에 연결되어 있는 다른 노드의 (가중치 노드 번호)들을 저장한다.
ex. 1과 4가 3의 가중치로 연결 : edges[1].push_back(3, 4); edges[4].push_back(3, 1);

2) 이 때 sum에 모든 가중치를 합하여 모든 도로가 연결되었을 때의 가중치 합을 계산한다.

3) edges 벡터에 대해 프림 알고리즘을 적용한다.

• 가중치의 오름차순으로 정렬되는 우선순위 큐 pq를 선언한다.
• 현재 노드를 저장하는 i를 선언하고 임의의 시작점으로 할 노드의 번호로 초기화한다. (해당 코드에서는 노드 1부터 시작) 그리고 현재까지 MST에 추가된 노드 개수를 저장하기 위한 count를 선언하고 1로 초기화 한다.
• count가 노드의 총 개수인 n보다 작은 동안 아래 과정을 반복한다.
  • 현재 노드를 mst에 추가한다.
  • 현재 노드에 연결된 간선들을 전부 확인해 상대 노드가 mst에 속해있지 않다면 우선순위 큐에 해당 간선을 삽입한다.
  • 만약 현재 노드에 연결된 간선들을 확인한 직후에도 우선순위 큐가 비어있다면 MST가 성립할 수 없는 경우이므로 sum을 -1로, answer를 0으로 초기화해 sum - answer가 -1이 나오도록 하고, 곧바로 프림 알고리즘을 종료한다.
  • 우선순위 큐에 있는 간선 중 하나를 꺼내서 우선순위 큐에서 제거한다. 해당 간선에 연결된 상대 노드가 아직 MST에 속해있지 않다면 해당 간선의 가중치를 answer에 누적시키고, i를 해당 간선에 연결된 상대 노드로 변경한다. 또한 count를 하나 증가시킨다.

4) 절약되는 금액인 sum - answer (== 모든 도로 연결 금액 - 최소 금액)를 출력한다.

🖥️ 풀이 코드

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

using namespace std;
typedef pair<int, int> pii;

vector<vector<pii>> edges;
bool mst[100001] ;
long long answer = 0, sum = 0;

void prim(int n)
{
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	int i = 1, count = 1;
	
	while (count < n)
	{
		mst[i] = true;
		for (int j = 0; j < edges[i].size(); j++)
		{
			int curNode = edges[i][j].second;
			
			if (!mst[curNode])
				pq.push(edges[i][j]);
		}

		if (pq.empty())		// 현재 노드의 간선들을 확인한 직후 우선순위 큐에 집어넣을 간선이 없으면
		{					// MST가 성립할 수 없는 경우이다.
			sum = -1;
			answer = 0;
			return;
		}

		for (int k = 0; k < pq.size(); k++)
		{
			pii curEdge = pq.top();
			pq.pop();

			if (!mst[curEdge.second])
			{
				answer += curEdge.first;
				i = curEdge.second;
				count++;
				break;
			}
		}
	}
}

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

	int n, m;
	cin >> n >> m;

	edges.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edges[a].push_back(pii(c, b));
		edges[b].push_back(pii(c, a));
		sum += c;		// 모든 간선 이을 때 간선 가중치의 총합
	}

	prim(n);
	cout << sum - answer;
}