🙇‍♀️원더랜드(Prim MST 알고리즘 : priority_queue 활용)

원더랜드에 문제가 생겼다.

원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.

원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.

어떤 도로는 도로를 유지보수하면 재정에 도움이 되는 도로도 존재한다.

재정에 도움이 되는 도로는 비용을 음수로 표현했다.

아래의 그림은 그 한 예를 설명하는 그림이다.

원더 랜드

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

▣ 입력설명
첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다. 

다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 

이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다. 

C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

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

▣ 입력예제 1 
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

▣ 출력예제 1
196

🚀풀이

prim 알고리즘을 이용해서 문제를 푼다.

prim알고리즘은 우선순위 큐를 이용한다.

일단 1번 정점은 추가한다.

그 뒤 1번 정점과 연결된 정점들을 우선순위 큐에 집어넣는데 최소값이 먼저오도록 한다.

이렇게 bfs 순회하듯 하면 완성됨.

이떄 한번 방문한 정점은 다시 들어오면 안된다.

priority_queue<Edge> pq;
vector<pair<int, int>> board[1000];
int n, m, a, b, cost, res = 0;
int ch[1000];

void solve()
{
	cin >> n >> m;

    // 양방향 인접리스크 그래프
	for (int i = 1; i <= m; ++i)
	{
		cin >> a >> b >> cost;
		board[a].push_back({ b, cost });
		board[b].push_back({ a, cost });
	}

    // 처음에는 가중치 없이 삽입
	pq.push({ 1, 0 });
	while (pq.empty() == false)
	{
		Edge edge = pq.top();
		pq.pop();
		int v = edge.v; // 정점
		int cost = edge.cost; // 정점까지 가는 비용
		if (ch[v]) // 한번 방문했으면 스킵
			continue;
		res += cost;
		ch[v] = 1;
		for (int i = 0; i < board[v].size(); ++i)
		{
			if (ch[board[v][i].first] == 0) // 방문 여부 확인
				pq.push({ board[v][i].first, board[v][i].second });
		}
	}

	cout << res;
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Edge
{
	int v;
	int cost;

	bool operator<(const Edge& other) const
	{
		return cost > other.cost;
	}
};

priority_queue<Edge> pq;
vector<pair<int, int>> board[1000];
int n, m, a, b, cost, res = 0;
int ch[1000];

void solve()
{
	cin >> n >> m;

	for (int i = 1; i <= m; ++i)
	{
		cin >> a >> b >> cost;
		board[a].push_back({ b, cost });
		board[b].push_back({ a, cost });
	}
	pq.push({ 1, 0 });
	while (pq.empty() == false)
	{
		Edge edge = pq.top();
		pq.pop();
		int v = edge.v;
		int cost = edge.cost;
		if (ch[v])
			continue;
		res += cost;
		ch[v] = 1;
		for (int i = 0; i < board[v].size(); ++i)
		{
			if (ch[board[v][i].first] == 0)
				pq.push({ board[v][i].first, board[v][i].second });
		}
	}

	cout << res;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고