[G4] 백준 3803번 Networking C++ MST, 최소 스패닝 트리, 크루스칼 알고리즘

리뷰

 

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

최근에 회사 내부 코드 컨벤션을 지키기 위해 노력하고 있다, 따라서 집에서도 로컬의 VS를 서식을 변경하였다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• nodes : 현재 노드가 속한 그룹의 번호를 저장하기 위한 배열
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• Edge : 간선 정보를 정의할 구조체, 가중치를 기준으로 오름차순 정렬한다.
• edges : 간선 정보를 저장할 Edge타입 벡터

 

함수

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

 

두 노드가 속한 그룹의 번호를 확인하고, 이미 같은 그룹이라면 pass, 아니라면 union을 진행하는 함수

 

 

문제풀이

1. while루프 조건으로 n값을 입력 받고, n이 0이 아니라면 루프를 계속 진행한다.
2. 매 루프마다 m값을 입력 받고, edges와 nodes를 초기화한다.
3. m개의 간선 정보를 입력 받아 edges에 push한다.
4. sort함수를 통해 edges를 가중치를 기준으로 오름차순 정렬한다.
5. 변수 sum, cnt를 0으로 초기화한다.
6. edges를 순회하며 두 노드의 번호와 가중치를 변수 f, t, w에 파싱한다.
7. Union함수에 f, t를 인자로 전달하고, 반환값이 true라면 sum에 w를 더해주고, cnt를 증가시킨다.
8. 만약 cnt가 n-1이라면 더 이상 탐색할 필요가 없으므로 break처리한다.
9. sum에 저장된 값을 출력하고, 개행문자를 삽입하여 줄바꿈을 수행한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. n은 최대 50, 가중치는 최대 100이고, 간선의 제한은 없다.

 

정답 코드

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

const int N = 51;
int nodes[ N ];
int n, m;
struct Edge
{
	int f, t, w;
	bool operator<( const Edge& other ) const
	{
		return w < other.w;
	}
};
vector< Edge > edges;

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

	edges.reserve( 100 );
	while ( ( cin >> n ) && n )
	{
		cin >> m;
		edges.clear();
		for ( int i = 1; i <= n; ++i )
			nodes[ i ] = i;

		while ( m-- )
		{
			int f, t, w;
			cin >> f >> t >> w;
			edges.push_back( { f, t, w } );
		}

		sort( edges.begin(), edges.end() );
		int sum = 0, cnt = 0;
		for ( const Edge& edge : edges )
		{
			const auto& [f, t, w] = edge;
			if ( Union( f, t ) )
			{
				sum += w;
				++cnt;
			}

			if ( cnt == n - 1 )
				break;
		}
		cout << sum << "\n";
	}
}