[C++] 백준 1197번: 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

CLASS 5에 진입하면서 새로운 알고리즘이 대거 등장하고 있다.

주어진 문제의 풀이를 스스로 생각하여 고안하기 보다는 새로운 알고리즘을 익히는 느낌으로 진행 중...

이번 문제는 다음 블로그의 글을 참고했다.

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

해당 글에서 소개된 두 가지 알고리즘을 각각 사용하여 이 문제를 풀어보았다.

먼저 시도한 알고리즘은 비교적 적은 간선에서 사용하기 유리한 Kruskal 알고리즘이다.

튜플 벡터로 모든 간선의 정보를 저장한 다음 가중치를 기준으로 오름차순 정렬을 진행했다.

정렬된 벡터에서 순서대로 간선의 정보를 읽으면서 양 끝 점을 union 해나가는 작업을 거쳐 답을 구할 수 있었다.

자료구조 시간에 배웠던 disjoint_set의 개념을 활용할 수 있었다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>
#define VP vector<pair<int, int>>
#define VVP vector<VP>
#define VB vector<bool>

/* declare variables here */
int V, E;
vector<tuple<int, int, int>> edges;

/* define debug functions here */


/* define functions here */
bool compare(const tuple<int, int, int>& lhs, const tuple<int, int, int>& rhs) {
	if (get<2>(lhs) < get<2>(rhs))
		return true;
	return false;
}

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	/* Write input codes here  */
	cin >> V >> E;
	// the edge connecting from A to B has weight C.
	edges = vector<tuple<int, int, int>>(E);
	FOR(i, E)
		cin >> get<0>(edges[i]) >> get<1>(edges[i]) >> get<2>(edges[i]);

	/* Write solution codes here */
	sort(edges.begin(), edges.end(), compare);
	VI connected(V + 1, -1);
	int sumOfWeight = 0;
	for (const auto& e : edges) {
		// take out the an edge
		const auto& [a, b, w] = e;
		// find the union root each vertex of the edge
		int group_a = a;
		while (connected[group_a] != -1)
			group_a = connected[group_a];
		int group_b = b;
		while (connected[group_b] != -1)
			group_b = connected[group_b];
		// check whether both vertex already connected
		if (group_a == group_b && group_a != -1)
			continue;
		// connect the edge
		if (group_a == -1)
			connected[group_a] = b;
		else
			connected[group_b] = a;
		sumOfWeight += w;
	}
	cout << sumOfWeight << EL;

	return 0;
}

그 다음으로 시도한 알고리즘은 비교적 많은 간선이 있을 때 유리한 Prim 알고리즘을 시도했다.

처음에는 인접행렬로 시도했으나, 메모리 초과로 실패했다. (정점의 개수가 최대 10,000)

그래서 인접리스트로 시도했고 두 번의 WA를 받았는데, 알고리즘 설명을 다시 읽어보니 현재 정점이 아닌 연결된 모든 정점에서의 간선 중 가중치가 제일 적은 것을 찾는 것이었다.

해당 설명대로 코드를 수정하여 연결된 정점을 저장하는 벡터를 만들고, 해당 벡터를 순회하면서 그 정점에 연결된 간선 중 가중치가 제일 작은 것을 찾아 다음 정점으로 이동했다.

하지만 이렇게 제출한 코드는 TL을 받았고, 질문검색을 통해 우선순위 큐를 이용해야 함을 깨달았다.

우선순위 큐를 선언하고 새로운 정점이 연결될 때마다 우선순위 큐에 그 정점과 연결된 모든 간선의 정보를 넣었다. (도착점, 가중치 순서로)

우선순위 큐에서 꺼낸 top element가 이미 방문한 정점과 이어지면 방문하지 않은 정점이 나올 때까지 다시 꺼낸다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>
#define VP vector<pair<int, int>>
#define VVP vector<VP>
#define VB vector<bool>

/* declare variables here */
int V, E;
VVP adj_list;

/* define debug functions here */


/* define functions here */
struct compare {
	bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
		return lhs.second > rhs.second;
	}
};


int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	/* Write input codes here  */
	cin >> V >> E;
	adj_list = VVP(V + 1);
	FOR(i, E) {
		int a, b, c;
		cin >> a >> b >> c;
		adj_list[a].push_back(make_pair(b, c));
		adj_list[b].push_back(make_pair(a, c));
	}

	/* Write solution codes here */
	int sumOfWeight = 0;
	VB mark(V + 1, false);
	priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
	for (const auto& adj : adj_list[1])
		pq.push(adj);
	mark[1] = true;
	while(!pq.empty()) {
		auto [minVertex, minWeight] = pq.top();
		pq.pop();
		if (mark[minVertex])
			continue;

		sumOfWeight += minWeight;
		for (const auto& adj : adj_list[minVertex])
			pq.push(adj);
		mark[minVertex] = true;
	}
	cout << sumOfWeight << EL;

	return 0;
}