[G3] 백준 13905번 세부 C++ MST, 최소 스패닝 트리

리뷰

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

최대값의 최소를 구하는 스패닝 트리 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• sn : 시작 노드의 번호를 저장할 변수
• en : 도착 노드의 번호를 저장할 변수
• Edge : 간선 정보를 정의할 구조체, 가중치를 기준으로 내림차순 정렬한다.
• edges : 간선 정보를 저장할 Edge타입 벡터
• nodes : 각 노드가 속한 그룹의 번호를 저장할 배열

 

함수

1. Find

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

 

노드가 속한 그룹의 번호를 찾고, 경로 압축을 수행해 주기 위한 함수

 

2. Union

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

 

두 노드가 속한 그룹의 번호를 찾고, 같다면 false를, 다르다면 그룹을 합쳐준 후 true를 반환하는 함수

 

 

문제풀이

1. n, m, sn, en값을 입력 받고, m개의 간선 정보를 입력 받아 edges벡터를 초기화한다.
2. sort함수를 통해 edges벡터를 가중치를 기준으로 내림차순 정렬한다.
3. nodes배열을 자기 자신을 값을 같도록 초기화한다.
4. 변수 mn을 100만보다 큰 값으로 초기화한다.
5. edges를 순회하며 변수 a, b, w에 구조체 정보를 파싱한다.
6. Union함수에 a, b를 전달하고, 반환값이 true인 경우 mn을 w와 비교해 더 작은 값으로 변경한다.
7. 만약 Find(sn)과 Find(en)의 반환값이 같다면 break처리한다.
8. 최종적으로 Find(sn)과 Find(en)의 반환값이 같다면 mn을, 다르다면 0을 출력한다.

 

트러블 슈팅

1. sn에서 en으로 갈 수 있는 길이 보장되어 있다고 생각하여 로직 작성 후 제출 시 WA를 받았다.
2. 만약 sn과 en이 같은 그룹에 속해있지 않는다면 도달할 수 없는 것으로 생각하여 로직 수정 후 제출 시 AC를 받았다.

 

참고 사항

1. 다리의 무게제한은 최소 1부터 최대 100만이다.
2. 숭이가 출발하여 혜빈이의 위치까지 도달할 수 있다는 보장이 없다.

 

정답 코드

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

const int N = 1e5 + 1;
int n, m, sn, en;
struct Edge {
	int a, b, w;
	bool operator<( const Edge& edge ) const {
		return w > edge.w;
	}
};
vector<Edge> edges;
int nodes[N];

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

	cin >> n >> m >> sn >> en;
	while (m--) {
		int a, b, w; cin >> a >> b >> w;
		edges.push_back( { a, b, w } );
	}
	sort( edges.begin(), edges.end() );

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

	int mn = 2e9;
	for (const Edge& edge : edges) {
		int a = edge.a, b = edge.b, w = edge.w;

		if (Union( a, b )) {
			mn = min( mn, w );
			if (Find( sn ) == Find( en )) break;
		}
	}
	cout << (Find( sn ) != Find( en ) ? 0 : mn);
}