백준 6497번 전력난 C++ MST, 최소 신장 트리

리뷰

MST인데 테스트케이스 여러개를 곁들인.. 문제였다. 예제만 보고 테케를 나눠주지 않아 첫시도에 틀렸다.

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

 

문제 풀이

1. 정답을 저장할 벡터 ans, 간선 정보를 저장할 edges, 간선 전체길이를 저장할 max_dist를 초기화 해준다.
2. while루프를 시작하고 1번에서 초기화한 리스트 들을 모두 초기값으로 변경해 준다.
3. n과 m 값을 받고 해당 값들이 모두 0일 경우 while루프를 종료한다.
4. 간선의 정보 m개를 가중치, 시작 노드, 종료 노드 순으로 edges 벡터에 tuple형태로 추가해 준다.
5. max_dist에 가중치를 더해주어 전체 길이를 최신화 해준다.
6. 간선 정보를 모두 받아왔으면 간선의 가중치를 기준으로 오름차순 정렬해 준다.
7. 이후 유니온 파인드를 통해 MST를 만들어 준 뒤 전체 간선의 가중치에서 MST 가중치를 빼준다.
8. 해당 값을 ans벡터에 전달해 주고 while루프가 종료될 때 까지 같은 작업을 반복해 준다.
9. while 루프가 종료되면 ans에 담긴 정보를 출력해 준다.

 

참고 사항

최소 비용을 구하는 것이 아닌 전체 비용에서 최소 비용을 빼준 값을 출력해 주어야 한다.

MST를 구하는 작업이 while 루프 안에서 이루어 져야 한다.

 

 

정답 코드

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

using namespace std;

int n, m;
int nodes[200001];

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(0);
	cin.tie(0);
	vector<int> ans;
	vector<tuple<int, int, int>> edges;
	int max_dist;
	while (1) {
		cin >> n >> m;
		if (n == 0 && m == 0) break;
		
		max_dist = 0;
		edges.clear();
		memset(nodes, 0, sizeof(nodes));
		for (int i = 0; i < m; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			edges.push_back({ c, a, b });
			max_dist += c;
		}

		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);
		}
		ans.push_back(max_dist - sum);
	}
	for (int an : ans) cout << an << "\n";
}