[C++] 원더랜드(Prim MST 알고리즘 : priority_queue 활용) ⭐

프림(Prim) 알고리즘은 그래프의 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 알고리즘 중 하나로, 시작 노드에서부터 출발하여 MST를 구성하는 과정을 설명합니다. 프림 알고리즘에서 priority_queue를 활용하는 것은 간선의 선택과 관련이 있습니다.

알고리즘 개요
1. 임의의 시작 노드를 선택하고, 해당 노드를 MST에 추가합니다.
2. MST에 속한 노드와 아직 MST에 포함되지 않은 노드 사이의 모든 간선 중에서 최소 가중치 간선을 선택합니다.
3. 선택한 간선의 도착 노드를 MST에 추가하고, 해당 노드를 MST의 일부로 만듭니다.
4. 위의 단계를 MST가 모든 노드를 포함할 때까지 반복합니다.

priority_queue의 활용
프림 알고리즘에서 각 단계마다 아직 MST에 속하지 않은 노드와 MST에 속한 노드 사이의 모든 간선 중에서 최소 가중치 간선을 찾아야 합니다. 이 때, priority_queue를 사용하여 최소 가중치 간선을 효율적으로 찾을 수 있습니다.
priority_queue는 최소 힙(Min Heap)의 형태로 간선들을 저장하며, 최소 가중치 간선을 상단에 유지합니다. 이렇게 하면 가장 작은 가중치의 간선을 빠르게 찾을 수 있습니다.
priority_queue에는 간선의 가중치와 연결된 노드의 정보가 저장되며, 각 단계에서 priority_queue에서 가장 작은 가중치 간선을 추출하여 MST에 추가합니다.

시간 복잡도
프림 알고리즘의 시간 복잡도는 주로 priority_queue의 연산에 의해 결정됩니다. priority_queue를 사용하면 간선의 추가와 추출이 각각 O(log(M)) 시간에 이루어집니다. 따라서 전체 시간 복잡도는 O(M * log(M))이 됩니다. 여기서 M은 간선의 수를 나타냅니다.

 

📄문제

원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.  
원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다. 어떤 도로는 도로를 유지보수하면 재정에 도움이 되는 도로도 존재한다. 재정에 도움이 되는 도로는 비용을 음수로 표현했다.  
아래의 그림은 그 한 예를 설명하는 그림이다.

위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.

 

⬇️ 입력

첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다. 다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

9 12 1 2 12 1 9 25 2 3 10 2 8 17 2 9 8 3 4 18 3 7 55 4 5 44 5 6 60 5 7 38 7 8 35 8 9 15

 

⬆️ 출력

모든 도시를 연결하면서 드는 최소비용을 출력한다.

196

 

📝 풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 노드에 방문 하였는지 검사
bool linked[101];

int main()
{
	vector<vector<pair<int, int>>> graph; // 그래프의 간선 정보 (도착지, 비용)
	priority_queue<pair<int, int>> q; // 우선순위 큐
	int cnt = 0;

	int V, E, sum = 0;
	scanf_s("%d %d", &V, &E);

	graph = vector<vector<pair<int, int>>>(V + 1);

	int f, t, w;
	for (int i = 0; i < E; ++i)
	{
		scanf_s("%d %d %d", &f, &t, &w);
		graph[f].push_back({ t, w });
		graph[t].push_back({ f, w });
	}

	q.push({ 0, 1 }); // 가중치가 0인 1로 가는 간선으로 시작

	while (cnt != V)
	{
		// 가장 가중치가 낮은 정보를 가져오기
		pair<int, int> data = q.top();
		q.pop();

		int weight = -data.first; // -data.first로 가중치 원본 가져오기
		int to = data.second; // 목적지

		// 이미 방문했던 노드라면 컨티뉴
		if (linked[to])
			continue;

		// 처음 방문하는 노드라면 진행

		sum += weight;
		++cnt;
		linked[to] = true;

		// 현재 위치에서 갈 수 있는 모든 간선 정보를 삽입
		for (int i = 0; i < graph[to].size(); ++i)
			q.push({ -graph[to][i].second, graph[to][i].first });
	}

	printf("%d", sum);
}

• 인접리스트를 이용하여 간선의 정보를 vector<vector....>> graph에 저장합니다. 인덱스 번호는 출발지, first는 목적지, second는 비용입니다.
• 우선순위 큐에 0, 1 더미데이터를 넣어 연산을 시작합니다. first는 비용, second는 목적지입니다.
• weight를 음수로 넣어 오름차순으로 정렬할 수 있도록 합니다.
• 각 큐에서 top을 통해 현재 목적지를 얻고, 현재 목적지로부터 갈 수 있는 모든 간선정보를 큐에 담습니다.
• 만약 도착한곳이 이미 다른 간선에 의해 도착했다면, 컨티뉴 합니다.