[백준] 6497-전력난(C++)

문제링크: https://www.acmicpc.net/problem/6497

6497번: 전력난

최소 스패닝 트리를 만드는 문제입니다.

 

접근방식

 

1. 최소 스패닝 트리 알고리즘에 대해서 인지하고 있어야 한다.

2. MST는 크게 크루스칼 알고리즘, 프림 알고리즘이 존재한다. 

3. 나는 그 중에서 우선순위 큐를 사용한 프림알고리즘으로 문제를 해결했다. 

 

문제풀이 

1. 우선순위 큐에 1과 인접한 그래프 삽입 

2. visited로 방문 여부를 판단하며, 정점 - 1 개까지 반복 

 일반적인 bfs와 흡사한 방식

3. 전체 비용의 합 - 최소 경로의 합

 

아래는 정답코드입니다.

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

vector <pair<int, int>> vec[200000];
bool visited[200000];
int m, n;
int result = 0;

void prim() {

	priority_queue <pair<int, int>> pq;
	visited[0] = true;
	for (int i = 0; i < vec[0].size(); i++) {
		pq.push(make_pair(-1 * vec[0][i].second, vec[0][i].first));
	}

	while (!pq.empty()) {
		int cost = pq.top().first * -1;
		int pos = pq.top().second;
		pq.pop();

		if (visited[pos] == false) {
			visited[pos] = true;
			result -= cost;
			
			for (int i = 0; i < vec[pos].size(); i++) {
				int ncost = vec[pos][i].second;
				int npos = vec[pos][i].first;
				if (visited[npos] == false)
					pq.push(make_pair(ncost*-1, npos));
			}

		}


	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	while (1) {
		cin >> m >> n;
		if (m == 0 && n == 0)
			break;

		for (int i = 0; i < m; i++)
			vec[i].clear();

		result = 0;
		int from, to, cost;
		for (int i = 0; i < n; i++) {
			cin >> from >> to >> cost;
			vec[from].push_back(make_pair(to, cost));
			vec[to].push_back(make_pair(from, cost));
			result += cost;
		}

		memset(visited, 0, sizeof(visited));
		
		prim();
		cout << result << endl;
	}

	
	return 0;
}