Back to Learn
바킹독 강의·

0x1B. 최소 신장 트리(MST) - Kruskal과 Prim

최소 신장 트리의 개념과 크루스칼/프림 알고리즘 구현을 정리한다.

알고리즘MST최소신장트리크루스칼프림

0x1B MST

0x00 정의와 성질

최소 신장 트리는 신장 트리 중에서 간선의 합이 최소인 트리를 의미한다. (이론적 분석은 최소 신장 트리 참고) 최소 신장 트리는 동일한 그래프에서 딱 한 개로 정해지지 않고 여러 개일 수 있다.

0x01 크루스칼 알고리즘

  1. 간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택
  2. 현재 선택한 간선이 정점 u, v를 연결하는 간선이라고 할 때 만약 u와 v가 같은 그룹이라면 아무것도 하지않고 넘어감, u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가
  3. 최소 신장 트리에 V-1개의 간선을 추가시켰다면 과정을 종료, 그렇지 않다면 그 다음으로 비용이 작은 간선을 선택한 후 2번 과정을 반복
#include <bits/stdc++.h>
using namespace std;

vector<int> p(10005,-1);

int find(int x){
  if(p[x] < 0) return x;
  return p[x]= find(p[x]);
}

bool is_diff_group(int u, int v){
  u= find(u); v= find(v);
  if(u= v) return 0;
  if(p[u]= p[v]) p[u]--;
  if(p[u] < p[v]) p[v]= u;
  else p[u]= v;
  return 1;
}

int v, e;
tuple<int,int,int> edge[100005];

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

  cin >> v >> e;
  for(int i = 0; i < e; i++){
    int a, b, cost;
    cin >> a >> b >> cost;
    edge[i] = {cost, a, b};
  }
  sort(edge, edge + e);
  int cnt = 0;
  int ans = 0;
  for(int i = 0; i < e; i++){
    int a, b, cost;
    tie(cost, a, b)= edge[i];
    if(!is_diff_group(a, b)) continue;
    ans = cost;
    cnt++;
    if(cnt= v-1) break;
  }
  cout << ans;
}

0x02 프림 알고리즘

  1. 임의의 정점을 선택해 최소 신장 트리에 추가
  2. 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장 트리에 추가
  3. 최소 신장 트리에 V-1 개의 간선이 추가될 때 까지 2번 과정을 반복
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int v, e;
vector<pair<int,int>> adj[10005]; // {비용, 정점 번호}
bool chk[10005]; // chk[i] : i번째 정점이 최소 신장 트리에 속해있는가?

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

  cin >> v >> e;
  for(int i = 0; i < e; i++){
    int a, b, cost;
    cin >> a >> b >> cost;
    adj[a].push_back({cost, b});
    adj[b].push_back({cost, a});
  }

  int cnt = 0; // 현재 선택된 간선의 수
  int ans = 0;
  // tuple<int,int,int> : {비용, 정점 1, 정점 2}
  priority_queue< tuple<int,int,int>,
                  vector<tuple<int,int,int>>,
                  greater<tuple<int,int,int>> > pq;

  chk[1] = 1;
  for(auto nxt : adj[1])
    pq.push({nxt.X, 1, nxt.Y});

  while(cnt < v - 1){
    int cost, a, b;
    tie(cost, a, b)= pq.top(); pq.pop();
    if(chk[b]) continue;
    ans = cost;
    chk[b]= 1;
    cnt++;
    for(auto nxt : adj[b]){
      if(!chk[nxt.Y])
        pq.push({nxt.X, b, nxt.Y});
    }
  }
  cout << ans;
}

0x03 연습문제 - BOJ 1368 물대기

물대기 문제1 물대기 문제2

간선을 하나 더 그리면 간단하게 풀린다.

문제 풀이

Note_ 21276 계보 복원가 호석 : find_index 함수를 정의해서 이름에 index를 매핑하려고 했지만 O(N)이 걸려서 시간초과가 났다. Hash map(map)으로 관리하면 이름을 인덱스로 바꾸는게 O(1)에 가능하게 된다는 것을 알았다.

map<key, value>

map<string, int> name_to_index;

// 이름을 인덱스로 매핑
for (int i = 0; i < n; i++)
    name_to_index[name[i]]= i;

cin >> m;
for (int i = 0; i < m; i++) {
    string a, b;
    cin >> a >> b;
    adj[name_to_index[b]].push_back(name_to_index[a]);
    deg[name_to_index[a]]++;
}

리뷰

출처: 바킹독님의 실전알고리즘 강의

바킹독 강의 Series26 posts