[BOJ] 백준 16398 행성 연결

문제 링크 : https://www.acmicpc.net/problem/16398

이 문제는, MST 즉 최소신장트리라고 하는 유형 입니다.

그래프가 주어졌을 때 모든 정점을 한번씩만 지나도록, 그리고 가중치의 합이 최소가 되도록 간선을 긋는 문제 입니다.

이 문제를 해결하기 위해서는 대표적으로 세가지 알고리즘이 있습니다.

- 1. 크루스칼 kruskal 알고리즘

- 2. 프림 prim 알고리즘

- 3. 솔린 sollin 알고리즘

저는 이 문제에서 크루스칼 알고리즘으로 해결을 했습니다.

 크루스칼 알고리즘은 그래프의 모든 간선들 중 가장 작은 가중치를 가지는 간선을 뽑고, 간선에 양 끝의 정점 2개가 같은 집합에 속하지 않았을 경우에만 간선을 긋는 알고리즘 입니다.

 프림 알고리즘은 정점별로 각 간선에 대한 오름차순으로 정렬된 배열을 가지고 있게 하고,

출발 정점에서 가장 가중치가 작은 간선에 연결된 정점과 간선을 긋고, 연결된 정점과 출발점에서 또 가장 가중치가 작은 간선에 연결된 정점과 간선을 긋는 알고리즘 입니다. 여기서, 정점끼리 같은 집합에 속하면 안됩니다.

 솔린 알고리즘은 그래프의 정점에서 돌아가면서 최소의 간선을 뽑는 알고리즘 입니다. 여기서 다른 정점끼리 같은 간선을 뽑을 수 있는데, 중복된 간선의 경우 pass 함으로써 중복을 제거합니다.

소스코드 : 

#include 
#include 
#include 
#include 
#include 
using namespace std;

struct Edge {
 int u, v, weight; 
 bool operator<(Edge const &e) {
  return weight < e.weight;
 }
};

// parent 기록 배열 선언
int parent[1001] ;

// parent 찾는 Find함수
int Find(int i) {
 if (i == parent[i]) return i;
 return parent[i] = Find(parent[i]);
}
// Merge
void Merge(int i, int j) {
 int ti = Find(i);
 int tj = Find(j);
 if (ti == tj) return;
 else {
  if (ti < tj) swap(ti, tj);
  parent[tj] = ti;
 }
}
int main() {
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 // parent 배열 초기화
 for (int i = 0; i < 1001; i++) {
  parent[i] = i;
 }
 int nv;
 cin >> nv ;

 // Edge 벡터에 값 넣음
 vector v;
 for (int i = 0; i < nv; i++) {
  for (int j = 0; j < nv; j++) {
   Edge e;
   e.v = i;
   e.u = j;
   cin >> e.weight;
   if(j > i)
    v.push_back(e);
  }
 }
 // 오름차순 정렬
 sort(v.begin(), v.end());

 int count = 0;
 long long sum = 0;

 for (int i = 0; i < v.size(); i++) {
  // 현재 간선 개수(count)가 정점의 개수인 nv보다 하나 작을때 탈출
  if (count == nv - 1) break;
  int pu = Find(v[i].u);
  int pv = Find(v[i].v);
  // parent가 다를 때 merge 후 거리를 합침.
  if (pu != pv) {
   Merge(pu, pv);
   sum += v[i].weight;
   count++;
  }
 }
 cout << sum << endl;
}