[G3] 백준 1833번 고속철도 설계하기 C++ 정렬, 유니온 파인드, MST, 최소 스패닝 트리

리뷰

 

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

엄청 오랜만에 풀어본 MST문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• arr : 간선 설치 비용을 저장할 2차원 정수 배열
• node : 집합 정보를 저장할 정수형 배열
• n : 노드의 개수를 저장할 변수
• Edge : 간선 정보를 정의할 구조체, 가중치를 기준으로 오름차순 정렬한다.

 

함수

1. Find

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

 

노드가 속한 그룹의 번호를 반환하고, 경로 압축을 수행하기 위한 함수

 

2. Union

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

 

두 노드가 속한 그룹의 번호를 비교하고, 합칠 수 있는지 여부를 반환하는 함수

 

 

문제풀이

1. n값을 입력 받고, 변수 sum, cnt를 0으로 초기화한다.
2. n*n크기의 인접 행렬을 입력 받아 arr배열을 초기화한다.
3. 이때 입력값이 음수인 경우 양수로 전환해 sum에 더해주고, 값을 0으로 초기화한다.
4. 인접 행렬로 인해 sum에는 간선 가중치가 두배로 인입되었으므로 2로 나누어준다.
5. Edge타입 벡터 edges를 초기화 하고, 인접 행렬을 대각선으로 갈라 edges를 초기화해준다.
6. sort함수를 통해 edges를 가중치 기준으로 오름차순 정렬해준다.
7. pair<int, int>타입 벡터 conn을 초기화한다.
8. node배열을 자기 자신의 인덱스를 값으로 갖도록 초기화한다.
9. edges를 순회하며 간선 정보를 변수 f, t, w에 파싱한다.
10. Union함수에 f, t를 매개변수로 전달하여 함수를 호출한다.
11. Union함수의 반환값이 true인 경우 sum에 w를 더해주고, cnt를 증가시킨다.
12. 만약 가중치가 0이 아닐 경우 conn애 {f, t}를 push해준다.
13. cnt가 n-1에 도달한 경우 break처리해준다.
14. sum과 conn.size()를 공백을 기준으로 출력하고, conn을 순회하며 개행문자를 삽입, pii정보를 공백을 기준으로 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 인접 행렬로 인해 sum에는 간선 가중치가 두배로 인입되었으므로 2로 나누어줬다.
2. 간선의 가중치는 최대 1만이므로 int범위 내로 비용 계산이 가능하다.

 

정답 코드

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

const int N = 201;
int arr[N][N];
int node[N];
int n;
struct Edge {
	int f, t, w;
	bool operator<(const Edge& other) const {
		return w < other.w;
	}
};

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

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

int main() {
	cin >> n;
	int sum = 0;
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			cin >> arr[i][j];
			if (arr[i][j] < 0) {
				sum += -arr[i][j];
				arr[i][j] = 0;
			}
		}
	}

	sum /= 2;
	vector<Edge> edges;
	for (int i = 1; i < n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			edges.push_back({ i, j, arr[i][j] });
		}
	}
	sort(edges.begin(), edges.end());

	vector<pair<int, int>> conn;
	for (int i = 1; i <= n; ++i) node[i] = i;
	for (const Edge& edge : edges) {
		int f = edge.f, t = edge.t, w = edge.w;

		if (Union(f, t)) {
			sum += w;
			++cnt;
			if (w) conn.push_back({ f, t });
		}

		if (cnt == n - 1) break;
	}
	cout << sum << " " << conn.size();
	for (const pair<int, int> pii : conn) {
		cout << "\n" << pii.first << " " << pii.second;
	}
}