BOJ 1197: 최소 스패닝 트리

✔ 문제 링크

BOJ 1197: 최소 스패닝 트리

---

✔ 문제해결전략

• Minimun Spanning Tree

---

✔ 해결과정

• 프림 혹은 크루스칼 알고리즘을 사용하여 MST를 구하면 된다.

---

✔ 정답 Code(Prim Algorithm)

#include <bits/stdc++.h>
using namespace std;

using ti3 = tuple<int, int, int>;

// weight, vertex
vector<pair<int,int> > adj[10001];
bool vis[10001];

void prim(int v, int e);

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int v, e;
  cin >> v >> e;

  for(int i=0;i<e;i++) {
    int a, b, c; // v1, v2, weight
    cin >> a >> b >> c;
    adj[a].push_back({c,b});
    adj[b].push_back({c,a});
  }

  prim(v, e);
}

void prim(int v, int e) {
  int cnt = 0;
  int total = 0;
  priority_queue<ti3, vector<ti3>, greater<ti3> > pq;

  // start from v1
  for(auto cur : adj[1])
    pq.push({cur.first, 1, cur.second});

  vis[1] = 1;

  while(1) {
    int weight, v1, v2;
    tie(weight, v1,v2) = pq.top();
    pq.pop();

    // case 1: already in MST -> do nothing
    if(vis[v2]) continue;

    // case 2: include v2
    vis[v2]=1;
    total += weight;
    cnt++;

    if(cnt==v-1) break;
    for(auto cur : adj[v2]) {
      if(!vis[cur.second])
        pq.push({cur.first, v2, cur.second});
    }
  }
  cout << total;
}

	

---

✔ 정답 Code(Kruskal Algorithm)

추가예정

---

✔ Comment

Priority Queue를 Min Heap으로 사용하려면

priority_queue<int, vector<int>, greater<int>> pq;

형태로 사용해야 한다고 해서 2번째 parameter의 vector는 뭔지, 3번째 parameter는 비교 함수 같긴 한데 정확히 뭐하는 함수인지 찾아보다가 또 모르는 게 나와서 찾아보기 시작하니 끝도 없다. C++ 제대로 사용하기 정말 어렵다..

또 Kruskal 알고리즘 구현하다 보니 disjoint set에서 union-find라는 것에 대해 알아야 해서 또 검색해 보니 시간이 살살 녹는다.

---

✔ 참고자료

https://blog.encrypted.gg/915?category=773649