[C/C++] 백준 - 1197번 (최소 스패닝 트리 - (프림))

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

1197번: 최소 스패닝 트리

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

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

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

 

다익스트라 알고리즘을 구현한 거와 같이 인접리스트 및 우선순위 큐를 활용하여 해결하였다.

처음에 가중치에 방향성이 있는 것으로 착각해 계속 틀렸습니다를 받았다. 문제를 다시 읽고 방향성이 존재하지 않는다는 것을 확인하고 solve를 받았다

 

다익스트라 알고리즘과 거의 유사하며, 다익스트라처럼 전의 이동거리를 저장하며 최소값을 탐색하고 저장하지 않아도 된다. 그냥 갈 수 있는 정점을 모두 확인하며 최소값의 비용이라면 바로 갱신시켜주면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<vector>
#include<queue>
#include<stdio.h>
#include<algorithm>
#define INF 2147483647

using namespace std;

// 프림 알고리즘을 사용한 최소 스패닝 트리
struct cmp {
	bool operator()(pair<int, int> lhs, pair<int, int> rhs) {
		if (lhs.first == rhs.first)
			return lhs.second > rhs.second;
		else
			return lhs.first > rhs.first;
	}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;

int ans[10003] = { INF };
bool visited[10003] = {false};
int V, E;

typedef struct graphNode {
	int dest;
	int cost;
	struct graphNode* next;
}GraphNode;

typedef struct graph {
	int count;
	GraphNode* adj;
}Graph;

void graph_init(Graph* gph, int count) {
	gph->count = count;
	gph->adj = (GraphNode*)malloc((count + 1) * sizeof(GraphNode));
	for (int i = 1; i <= count; i++)
		gph->adj[i].next = NULL;
}

int AddDirectedEdge(Graph* gph, int src, int dst, int cost) {
	GraphNode* temp = (GraphNode*)malloc(sizeof(GraphNode));
	temp->cost = cost;
	temp->dest = dst;
	temp->next = gph->adj[src].next;
	gph->adj[src].next = temp;
	return 1;
}

int AddUnDirectedEdge(Graph* gph, int src, int dst, int cost) {
	return AddDirectedEdge(gph, src, dst, cost) && AddDirectedEdge(gph, dst, src, cost);
}

void PrintGraph(Graph* gph) {
	GraphNode* head;
	for (int i = 1; i <= V; i++) {
		head = gph->adj[i].next;
		printf("Node [ %d ] : ", i);
		while (head) {
			printf(" %d(%d) ", head->dest, head->cost);
			head = head->next;
		}
		cout << '\n';
	}
}

void FindminValue(Graph* gph, int start) {
	GraphNode* head = gph->adj[start].next;
	while (head) {
		if (visited[head->dest]==false && head->cost < ans[head->dest]) {
			ans[head->dest] = head->cost;
			pq.push({ ans[head->dest], head->dest });
		}
		head = head->next;
	}
}

long long result() {
	long long total = 0;
	for (int i = 1; i <= V; i++) {
		total += ans[i];
	}
	return total;
}

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

	Graph graph;
	cin >> V >> E;
	graph_init(&graph, V);


	for (int i = 0; i < E; i++) {
		int from, to, value;
		cin >> from >> to >> value;
		AddUnDirectedEdge(&graph, from, to, value);
	}
	//PrintGraph(&graph);
	// 아무 시작 지점을 선정, 난 1로 하겠음
	for (int i = 1; i <= V; i++) ans[i] = INF;
	ans[1] = 0;
	pq.push({ ans[1], 1 });

	while (!pq.empty()) {
		int start = pq.top().second;
        visited[start] = true;
		pq.pop();

		FindminValue(&graph, start);
	}
	cout << result() << '\n';

	return 0;
}