[G3] 백준 13418번 학교 탐방하기 C++ 최소 스패닝 트리(MST), 정렬

리뷰

 

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

크루스칼 알고리즘으로 문제를 풀이하였다. 문제에 함정이 많다. 조심!

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 건물의 개수를 저장할 변수
• m : 도로의 개수를 저장할 변수
• Edge : 간선 정보를 정의할 구조체
• edges : 간선 정보를 저장할 Edge타입 벡터
• nodes : 각 건물이 속한 그룹 정보를 저장할 배열

 

함수

1. best

bool best(const Edge& left, const Edge& right) {
	return left.v < right.v;
}

 

간선을 내리막길을 기준으로 정렬하기 위한 함수

 

2. worst

bool worst(const Edge& left, const Edge& right) {
	return left.v > right.v;
}

 

간선을 오르막길을 기준으로 정렬하기 위한 함수

 

3. Find

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

 

현재 건물이 속한 그룹의 번호를 반환하기 위한 함수

 

4. Union

bool Union(int a, int b) {
	int A = Find(a);
	int B = Find(b);
	if (A == B) return false;
	if (A > B) swap(A, B);
	nodes[B] = A;
	return true;
}

 

두 건물을 그룹화 시켜주기 위한 함수

 

 

문제풀이

1. n, m값을 입력 받고, m을 1만큼 증가시킨 뒤 m만큼의 while루프를 수행해 준다.
2. m개의 간선 정보를 입력 받아 edges벡터에 양방향 간선으로 추가해 준다.
3. n개의 노드에 대해 nodes배열을 자기 자신을 값을 갖도록 초기화를 진행해 준다.
4. best_val, best_conn을 0으로 초기화해 준 후 sort함수를 통해 edges벡터를 best함수를 사용해 정렬해 준다.
5. edges를 순회하며 Union함수에 두 건물의 번호를 매개변수로 전달해 준다.
6. Union함수는 두 건물의 번호를 각각 변수 a, b로 전달 받고, Find함수에 매개변수로 전달해 준다.
7. 변수 A, B에 a, b가 속한 그룹의 번호를 저장하고, A와 B가 같다면 false를 리턴해 준다.
8. 같지 않다면 A, B를 크기에 따라 정렬해 주고 nodes[B]의 값을 A로 저장 후 true를 리턴해 준다.
9. Union함수의 리턴값이 true일 경우 best_val에 간선의 가중치를 더해주고, best_conn을 증가시킨다.
10. best_conn이 n일 경우 더 이상 탐색하지 않고 break처리해 준다.
11. worst케이스도 동일하게 진행되나 변수명과 정렬 시 사용할 함수가 worst인 부분만 다르다.
12. worst_val^2 - best_val^2의 결과를 출력해 준다.

 

트러블 슈팅

1. 1이 오르막길, 0이 내리막길로 인지하여 풀었더 Fail을 받았다.
2. 문제를 다시 읽어보니 C는 0(오르막길) 또는 1(내리막길)의 값을 가진다는 조건이 있었다.
3. edges에 가중치를 추가할 때 not연산(!c)을 통해 반전시켜 주니 AC를 받았다.

 

참고 사항

1. 숫자 0이라는 입구 개념이 있으므로 n, m값보다 노드의 개수는 1개, 도로의 개수는 1개가 더 많다.
2. 오르막길도 1이 아닌 0이므로 문제를 잘 읽고 풀어야 한번에 AC를 받을 수 있을 듯 하다.

 

정답 코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

const int N = 1e3 + 5;
int n, m;
struct Edge {
	int cn, nn, v;
};
vector<Edge> edges;
int nodes[N];

bool best(const Edge& left, const Edge& right) {
	return left.v < right.v;
}

bool worst(const Edge& left, const Edge& right) {
	return left.v > right.v;
}

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

bool Union(int a, int b) {
	int A = Find(a);
	int B = Find(b);
	if (A == B) return false;
	if (A > B) swap(A, B);
	nodes[B] = A;
	return true;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;

	++m;
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		edges.push_back({ a, b, !c });
		edges.push_back({ b, a, !c });
	}

	for (int i = 0; i <= n; ++i) nodes[i] = i;
	int best_val = 0, best_conn = 0;
	sort(edges.begin(), edges.end(), best);
	for (const Edge& edge : edges) {
		if (Union(edge.cn, edge.nn)) {
			best_val += edge.v;
			best_conn++;
		}
		if (best_conn == n) break;
	}

	for (int i = 0; i <= n; ++i) nodes[i] = i;
	int worst_val = 0, worst_conn = 0;
	sort(edges.begin(), edges.end(), worst);
	for (const Edge& edge : edges) {
		if (Union(edge.cn, edge.nn)) {
			worst_val += edge.v;
			worst_conn++;
		}
		if (worst_conn == n) break;
	}

	cout << pow(worst_val, 2) - pow(best_val, 2);
}