백준 1922번 네트워크 연결 C++ MST, 최소 신장 트리

리뷰

아주 기초적인 MST 문제, 최소 스패닝 트리를 만든 후 각 간선의 가중치의 합을 출력하면 된다.

 

문제 풀이

1. 컴퓨터의 수는 최대 1000개 까지 주어지므로 1001 크기의 정수형 배열 nodes를 전역으로 초기화 해준다.
2. n과 m 값을 받아오고 정수 세개를 인자로 받는 tuple의 1차 벡터 배열인 edges를 초기화 해준다.
3. m개의 정보 출발 노드, 도착 노드, 간선의 가중치를 edges 배열에 가중치, 시작 노드, 도착 노드 순으로 추가한다.
4. edges 벡터를 오름차순으로 정렬해 준다.
5. nodes를 1부터 N까지 각각의 인덱스에 자기 인덱스를 value로 갖게끔 갱신해 준다.
6. 간선의 가중치 합을 저장할 정수형 변수 sum을 0으로 초기화 해준다.
7. 다시 간선의 개수 m개 만큼 for문을 시작하고, 각 간선의 정보를 조회해 준다.
8. 만약 현재 간선의 시작 노드와 도착 노드의 루트 노드가 동일하다면 이미 MST에 추가되어 있다는 말이므로 continue
9. 만약 루트 노드가 상이하다면 Union 처리를 해준 후 sum에 해당 간선의 가중치를 더해준다.
10. 이를 모든 간선에 대해 동일한 작업을 처리해 주고 for문이 종료된 후 sum에 저장된 값을 출력해 주면 된다.

 

참고 사항

tuple에 가중치를 첫번째 인자로 넣어 주면 sort로 정렬할 경우 알아서 가중치를 기준으로 오름차순 정렬해 준다.

가중치를 기준으로 오름차순 정렬이 되어 있기에 루트 노드가 다르다면 MST에 순차적으로 넣어주면 된다.

MST에 넣어준 후엔 반드시 Union을 통해 MST에 추가가 되었 다는것을 체크해 주어야한다.

 

정답 코드

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

using namespace std;

int nodes[1001];
int n, m;

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 >> m;

	vector<tuple<int, int, int>> edges;
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		edges.push_back({ c, a, b });
	}
	sort(edges.begin(), edges.end());

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

	int sum = 0;
	for (int i = 0; i < m; 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;
}