백준 16398 c++ "행성 연결" -PlusUltraCode-

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

[필자 사고]

mst문제다.

mst의 핵심 개념은 모든 노드들을 최소의 가중치를 가지고 연결하는 형태다. 

군집화는 어떻게 해야 될가??
먼저 모든 조합들을 하나의 vector에 넣은 뒤 sort을  가중치 기준으로 오름차순 정렬을 한다.

그리고 각 군집들이 동일한 parent가 아닐경우 union을 해주고 값을 갱신해주느 형태로 문제를 타파했따.

 

아래는 자세한 코드 해설이다.

[코드 해설]

1. struct Node

• 간선 하나를 표현하는 구조체이다.
• start, end, weight를 멤버로 가진다. 각각 시작 정점, 끝 정점, 가중치(거리 또는 비용)를 의미한다.
• operator<를 오버로딩하여 sort에서 가중치를 기준으로 오름차순 정렬이 가능하도록 한다.

---

2. vector<int> parent 와 Union-Find 함수들

• parent는 서로소 집합(Union-Find)을 구현하기 위한 배열이다.
• find(int a)는 노드 a가 속한 집합의 루트 노드를 찾는다. 경로 압축을 적용하여 탐색 속도를 최적화한다.
• Union(int a, int b)는 두 집합을 하나로 합친다. 두 루트가 다를 때만 합친다.
• isSame(int a, int b)는 두 노드가 같은 집합에 속해 있는지 확인한다. 같은 집합이면 true, 아니면 false를 반환한다.

---

3. int N 과 입력

• N은 정점(노드)의 개수를 의미한다.
• map은 N x N 인접 행렬 형태로 입력을 받는다. map[i][j]는 정점 i와 정점 j를 잇는 간선의 비용이다.
• 모든 정점 쌍에 대해 비용이 주어진다고 가정한다.

---

4. 간선 리스트 생성

• 이중 for문을 돌면서 i에서 k로 가는 간선을 모두 벡터 arr에 저장한다.
• 단, 자기 자신으로 가는 간선(i == k)은 제외한다.
• 결과적으로 arr에는 전체 그래프의 모든 간선 정보가 들어간다.

---

5. Kruskal 알고리즘 준비

• arr를 가중치 기준으로 오름차순 정렬한다.
• parent 배열을 초기화하여 각 노드가 자기 자신을 부모로 가지도록 한다.

---

6. MST 구성

• 정렬된 간선들을 하나씩 확인하면서,
  • 만약 두 정점이 아직 같은 집합이 아니면(isSame == false), Union을 수행하고 MST 비용에 그 간선의 가중치를 더한다.
  • 이미 같은 집합이라면 사이클이 생기므로 무시한다.
• 이렇게 하면 최소 스패닝 트리가 완성된다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;

typedef struct Node {
	int start;
	int end;
	int weight;

	bool operator<(Node& other) {
		return weight < other.weight;
	}
}Node;

vector<int> parent;

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

int N;
vector<Node> arr;
vector<vector<int>> map;

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

	cin >> N;
	map.assign(N, vector<int>(N));

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> map[i][k];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (i == k)continue;
			arr.push_back({ i,k,map[i][k] });
		}
	}

	sort(arr.begin(), arr.end());
	parent.assign(N,0);
	for (int i = 0; i < N; i++) {
		parent[i] = i;
	}
	ll mst = 0;
	for (int i = 0; i < arr.size(); i++) {
		if (!isSame(arr[i].start, arr[i].end)) {
			Union(arr[i].start, arr[i].end);
			mst += arr[i].weight;
		}
	}
		
	cout << mst;
}