백준 1922 c++ "네트워크 연결" -PlusUltraCode-

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

 

[필자 사고]

최소 스패닝 트리를 이용하며 쉽게 해결할 수 있다.

 

필자는 입력 받은 가중치들을 벡터에 오름차순으로 정렬 하였다.

**** 실수 조심 >> 그 뒤 start와 end 값이 같으면 무시하고 

start 와 end 가 현재 같은 Union인지 아닌지를 판다하여 문제를 해결해 나갔다.

 

아래는 코드 해설이다.

설명

1. 크루스칼 알고리즘 개요:
   • 크루스칼 알고리즘은 가중치가 있는 그래프에서 **최소 스패닝 트리(MST)**를 구하는 알고리즘 중 하나입니다.
   • 먼저 모든 간선을 가중치 순서대로 정렬한 후, 사이클을 만들지 않으면서 최소 가중치 간선을 하나씩 선택하여 트리를 만들어 나갑니다.
   • 이를 위해 유니온-파인드(Union-Find) 자료구조를 사용해 사이클을 확인하고, 노드들이 같은 집합에 속해 있는지 확인합니다.

코드 흐름

1. 구조체 정의 (Edge):
   • Edge 구조체는 간선의 시작점(start), 끝점(end), 그리고 가중치(weight)를 저장합니다.
2. 전역 변수:
   • N: 노드의 수.
   • M: 간선의 수.
   • resultWeight: 최종적으로 구할 최소 스패닝 트리의 가중치 합.
   • arr: 모든 간선 정보를 저장하는 벡터.
   • parent: 각 노드의 부모 노드를 저장하는 벡터로, 유니온-파인드에서 사용됩니다.
3. 입력 처리 (Input 함수):
   • 먼저 노드와 간선의 수를 입력받고, 각 노드를 자기 자신이 부모인 상태로 초기화합니다.
   • 이후 각 간선의 정보를 입력받아 arr 벡터에 저장합니다.
4. 정렬 함수 (cmp 함수):
   • arr 벡터에 있는 간선들을 가중치(weight) 기준으로 오름차순 정렬하기 위해 비교 함수를 정의합니다.
5. 유니온-파인드(Union-Find) 함수:
   • find(int a): 노드 a의 부모 노드를 찾는 함수로, 경로 압축(Path Compression)을 사용해 탐색 속도를 빠르게 만듭니다.
     • 부모 노드를 재귀적으로 찾아가며, 중간 노드들도 최상위 부모로 연결합니다.
   • Union(int a, int b): 두 노드 a와 b를 같은 집합으로 합칩니다. 부모가 다를 경우에만 합집합 연산을 수행합니다.
   • isSame(int a, int b): 두 노드 a와 b가 같은 집합에 속하는지 확인하여 사이클 여부를 판단합니다. 같은 집합에 있으면 true, 아니면 false를 반환합니다.
6. 크루스칼 알고리즘 (SpanningTree 함수):
   • 1단계: 먼저 모든 간선들을 가중치 오름차순으로 정렬합니다.
   • 2단계: 정렬된 간선들 중에서 가중치가 작은 것부터 하나씩 확인합니다. 만약 두 노드가 같은 집합에 속해 있지 않으면, 그 간선을 선택하고 가중치를 resultWeight에 더합니다.
   • 사이클이 발생하는 간선은 건너뛰며, 최종적으로 모든 노드를 연결하는 최소 스패닝 트리가 구성됩니다

 

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
	int start;
	int end;
	int weight;
};

int N, M;
int resultWeight = 0;
vector<Edge> arr;
vector<int> parent;

bool cmp(Edge a, Edge b) {
	return a.weight < b.weight;
}

int find(int a) {
	if (a == parent[a])return a;
	return parent[a] = find(parent[a]);
}
void Union(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		parent[b] = a;
	}
}
bool isSame(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return true;
	return false;
}


void Input() {
	cin >> N >> M;
	parent.resize(N + 1);

	for (int i = 0; i <= N; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		arr.push_back({ s,e,w });
	}
}

void SpanningTree() {
	sort(arr.begin(), arr.end(), cmp);

	for (int i = 0; i < arr.size(); i++) {
		Edge nowEdge = arr[i];
		int start = nowEdge.start;
		int end = nowEdge.end;
		int weight = nowEdge.weight;
		if (start == end)continue;
		if (isSame(start, end) == false) {
			Union(start, end);
			resultWeight += weight;
		}
	}
}

void GameStart() {
	SpanningTree();
	cout << resultWeight;
}

int main(void) {
	Input();
	GameStart();
}