백준 16398번 행성 연결 C++ MST, 최소 신장 트리

리뷰

인접 행렬을 입력받아 최소 신장 트리를 구하는 문제

 

문제 풀이

1. 행성의 최대 수는 1000이니 nodes 배열을 1001 크기로 초기화 해준다.
2. 정수 인자 3개를 받는 튜플을 인자로 갖는 벡터 edges를 초기화 해준다.
3. n값을 입력 받고 n * n 크기의 for문을 개행하여 값을 받아준다.
4. 단방향 간선을 받아도 무방하기에, j >= i 인 경우 가중치, 시작, 종료 노드를 튜플 형태로 edges 벡터에 추가한다.
5. edges 벡터를 오름차순으로 정렬하고 nodes의 각 노드들의 value를 자기 자신을 갖도록 초기화 해준다.
6. 최소 가중치 합을 저장할 sum 변수를 0으로 초기화 하고 해당 변수에 최소 신장 트리의 가중치 합을 더한다.
7. 이후 sum을 출력해 준다.

 

참고 사항

가중치는 최대 1억이 주어지기 때문에 int 타입을 벗어날 확률이 크다, long long 타입으로 설정하자.

 

 

정답 코드

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

int nodes[1001];
int n;

vector<tuple<int, int, int>> lst;

int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

void Union(int a, int b) {
	int rootA = Find(a);
	int rootB = Find(b);
	if (rootA == rootB) return;
	nodes[rootB] = rootA;
}

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

	cin >> n;

	vector<tuple<int, int, int>> edges;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int c;
			cin >> c;
			if (j >= i && c) edges.push_back({ c, i, j });
		}
	}
	sort(edges.begin(), edges.end());

	for (int i = 1; i <= n; i++) {
		nodes[i] = i;
	}

	long long sum = 0;
	for (int i = 0; i < edges.size(); i++) {
		tuple<int, int, int> cur = edges[i];
		if (Find(get<1>(cur)) == Find(get<2>(cur))) continue;
		Union(get<1>(cur), get<2>(cur));
		sum += get<0>(cur);
	}
	cout << sum;
}