[G3] 백준 9344번 도로 C++ 최소 스패닝 트리, MST

리뷰

 

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

MST가 보장될 때 특정 간선이 MST에 포함되는지 여부를 체크하는 문제

 

 

전역 변수

• t : 테스트 케이스의 개수를 저장할 정수형 변수
• n : 각 테스트 케이스 마다 도시의 개수를 저장할 정수형 변수
• m : 각 테스트 케이스 마다 도로의 개수를 저장할 정수형 변수
• p, q : 각 테스트 케이스 마다 도로가 MST에 포함되는지 여부를 결정할 두 도시의 번호를 저장할 정수형 변수
• nodes : 각 도시의 그룹화를 진행하기 위한 정수형 배열
• Edge : 간선 정보를 정의하기 위한 구조체 두 노드 정보 cn, nn와 가중치 w를 갖고, w기준으로 오름차순으로 정렬하는 operator 함수를 정의해 준다.

 

함수

1. Find

int Find(int a)

 

현재 도시가 어떤 그룹에 속해 있는지를 찾기 위한 함수

1. 매개 변수로 도시의 번호 a를 전달 받는다.
2. 현재 도시의 번호가 자기 자신을 그룹으로 갖고 있다면 도시의 번호를 리턴해 준다.
3. 만약 다른 그룹에 속해 있다면 경로 압축을 통해 그룹를 최신화를 해주고 속한 그룹의 번호를 리턴해 준다.

 

2. Union

bool Union(int a, int b)

 

두 도시가 속한 그룹을 탐색하고, 그룹화를 진행하기 위한 함수

1. 매개 변수로 두 도시의 번호 a, b를 전달 받는다.
2. 정수형 변수 A, B에 Find함수를 통해 각각의 도시가 속한 그룹의 번호를 찾아 저장해 준다.
3. 만약 A와 B가 동일하다면 이미 동일 그룹에 속한 것이기 때문에 false를 리턴해 준다.
4. A와 B가 다르다면 B가 속한 그룹을 A로 변경해 준 뒤 true를 리턴해 준다.

 

문제풀이

1. t를 입력 받고, t번의 while문을 통해 각 테스트 케이스를 수행해 준다.
2. 각 테스트 케이스 마다 n, m, p, q에 값을 입력 받아준다.
3. p가 q보다 클 경우 swap을 통해 p가 항상 더 작은 번호로 유지되도록 변경해 준다.
4. nodes배열을 각 도시가 자기 자신을 그룹으로 갖도록 초기화를 진행해 준다.
5. Edge타입의 벡터 edges를 n + 1크기로 초기화 해준다.
6. m번의 while 루프를 수행하여 m개의 간선 정보를 변수 a, b, c에 입력 받는다.
7. 만약 a가 b보다 크다면 swap을 통해 a가 항상 더 작은 번호로 유지되도록 변경해 준다.
8. edges에 간선 정보를 push해준다.
9. 모든 간선 정보를 입력 받았다면 sort함수를 통해 가중치를 기준으로 오름차순 정렬해 준다.
10. 정수형 변수 cnt를 0으로 초기화 해주고, 논리형 변수 flag를 0(false)로 초기화 해준다.
11. 모든 간선 정보를 순회하며 각 도시를 Union함수의 인자로 전달하여 호출을 진행한다.
12. 만약 함수의 리턴값이 true라면 cnt를 증가시키고, 도시의 번호가 p, q라면 flag를 1(true)로 변경해 준다.
13. cnt가 n - 1에 도달했을 경우 MST가 완성된 경우이므로 break를 처리해 준다.
14. flag가 true라면 YES를, false라면 NO를 출력해 주고 줄 바꿈을 실행해 준다.
15. 모든 테스트 케이스가 종료될 때 까지 위 로직을 수행해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• swap을 통해 항상 1번 도시를 기준으로 그룹화가 진행 되도록 구현해 주었다.

 

정답 코드

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

int t, n, m, p, q;
int nodes[10001];
struct Edge {
	int cn, nn, w;
	bool operator<(const Edge& other) const {
		return w < other.w;
	}
};

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;
	nodes[B] = A;
	return true;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> t;
	while (t--) {
		cin >> n >> m >> p >> q;
		if (p > q) swap(p, q);
		for (int i = 1; i <= n; ++i) nodes[i] = i;
		vector<Edge> edges(n + 1);
		while (m--) {
			int a, b, c; cin >> a >> b >> c;
			if (a > b) swap(a, b);
			edges.push_back({ a, b, c });
		}
		sort(edges.begin(), edges.end());

		int cnt = 0;
		bool flag = 0;
		for (const Edge& edge : edges) {
			if (Union(edge.cn, edge.nn)) {
				cnt++;
				if (edge.cn == p && edge.nn == q) flag = 1;
			}
			if (cnt == n - 1) break;
		}

		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}
}