[ 백준 1197 ] 최소 스패닝 트리 (C++) - 최소 스패닝 트리

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. 문제에서 최소 스패닝 트리라고 나와 있으므로 같은 방식으로 풀면 좋다.
2. 사실 최소 스패닝 트리가 기억이 잘 나지 않지만, 일단 트리 형식을 갖추면서 가중치가 가장 적은 트리를 만들어야 한다는 것을 알 수 있다.
3. 그러면 최대한 낮은 비용의 간선부터 연결해야 한다.
4. 단, 간선을 연결할 때, Cycle이 생기면 안된다. => Root가 같은 것들끼리는 연결해서는 안된다.
5. 따라서 비용을 오름차순으로 정렬하고 4번을 지키면서 낮은 것들을 계속 연결해가면 된다.
6. 단, 매번 부모를 계속 찾을 수 없으므로 매번 현재 나의 Root가 무엇인지 업데이트 해준다.

---

⭐️ 정답 코드 및 설명

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

using namespace std;

int V, E;

vector<pair<int, pair<int, int>>> edges; // cost, V1, V2
int root[10001];

void input() {
    cin >> V >> E;

    // 일단, 처음엔 모두 자기 자신이 Root다.
    for (int i = 1; i <= V; i++) { 
        root[i] = i;
    }

    for (int i = 0; i < E; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        edges.push_back({C, {A, B}});
    }

    // 비용 기준으로 오름차순
    sort(edges.begin(), edges.end());
}

// 부모를 찾는 메서드
int getRoot(int x) {
    if (root[x] == x) return x;
    return root[x] = getRoot(root[x]); // 매번 업데이트
}

long long sol() {
    int cost, A, B;
    long sum = 0;
    for (auto edge : edges) {
        cost = edge.first;
        A = edge.second.first;
        B = edge.second.second;
        if (getRoot(A) != getRoot(B)) { // 부모가 다르다면
            sum += cost;
            root[getRoot(B)] = getRoot(A); // 부모를 업데이트해준다.
        }
    }
    return sum;
}

int main() {
    input();
    cout << sol();
    return 0;
}

---

🤔 문제 후기

root[getRoot(B)] = getRoot(A); 이 부분에서 root[B] = getRoot(A);로 풀어서 너무 오래 걸렸다. 다른 부분은 10~20분 만에 작성하였는데, 해당 부분을 고치는데 1시간이 걸린 것 같다. 처음에는 당연히 B가 A의 루트로 업데이트 되니 문제 없을 것이라고 생각했지만, https://www.acmicpc.net/board/view/139913 이곳의 반례를 보고 B의 루트를 바꿔줘야 하는 것을 알았다. 그래야 나중에 1->2->6->4->8 이런식으로 나왔을 때, 3->7->8 으로 연결하고 1->3 으로 연결할 때, 문제가 생기지 않는다.(루트는 1이다.) 설명을 잘 못한 것 같은데, 해당 반례를 보고 node의 좌표를 찍어보면 이해하면 할 수 있을 것이다.