certmin

문제 소개

V개의 정점과 E개의 간선으로 이루어진 가중치 그래프가 주어질 때, 최소 스패닝 트리(MST) 의 가중치 합을 구하는 문제다.

여기서 스패닝 트리(Spanning Tree)란, 그래프의 모든 정점을 포함하면서 사이클이 없는 부분 그래프다. 정점이 V개라면 간선은 정확히 V-1개가 된다. 여기서 간선 가중치의 합이 최소인 것을 최소 스패닝 트리(MST) 라고 한다

접근: 왜 DFS가 아닌가

그래프 문제를 보면 반사적으로 BFS / DFS를 먼저 떠올리게 된다. 하지만 DFS는 "모든 노드를 방문"하는 데는 쓸 수 있어도, 전체 가중치의 합을 최소화 하는 최적해를 보장하지 않는다. 다른 접근이 필요하다.

알고리즘 선택: 프림(Prim) vs 크루스칼(Kruskal)

MST를 구하는 대표적인 두 알고리즘이다.

프림(Prim): 정점을 하나씩 추가하며 트리를 키워나가는 방식 (우선순위 큐 활용)
크루스칼(Kruskal): 가중치가 작은 간선부터 그리디하게 선택하는 방식

struct 를 만들고 정렬하는 흐름에 이미 익숙해져 있었기 때문에, 간선 중심인 크루스칼이 더 직관적으로 다가왔다.

핵심 난관: 사이클 판정과 유니온 파인드(Union-Find)

크루스칼에서 간선을 무작정 추가하다 보면 사이클이 생길 위험이 있다. 이미 같은 컴포넌트에 속한 두 정점을 다시 잇는 순간 트리가 아니게 된다. 이를 처리하기 위해 유니온 파인드(Disjoint Set) 를 학습했다.

💡 C++ 발견 1 — 대입 연산자의 반환값과 경로 압축(Path Compression)

find 함수를 구현하면서 신기했던 순간.

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]); // 경로 압축
}

C++에서 대입 연산자(=)는 값을 할당하고 그 값을 그대로 반환한다. 이 성질 덕분에 parent[x] 를 갱신하는 동시에 그 값을 return 하는 원라이너가 가능하다.

경로 압축이 왜 빠른지 이해하려면 먼저 유니온 파인드의 기본 구조를 알아야 한다. 각 노드는 자신의 부모를 가리키고, 루트 노드는 자기 자신을 가리킨다. find(x) 는 이 부모 포인터를 타고 올라가 루트를 찾는 함수다.

압축 없이 단순하게 구현하면 트리가 한쪽으로 치우칠 수 있다. 예를 들어 1 → 2 → 3 → 4 → 5 처럼 일자로 늘어진 경우, find(1) 은 루트까지 4번을 거슬러 올라가야 한다. 최악의 경우 $O(V)$다.

// 압축 없는 버전
int find(int x){
    if(parent[x] == x) return x;
    return find(parent[x]);
}

경로 압축은 find 가 루트를 찾아 돌아오는 길에 거쳐온 모든 노드의 부모를 루트로 직접 연결한다. 1 → 2 → 3 → 4 → 5 였던 트리가 find(1) 한 번으로 1, 2, 3, 4 모두 5를 직접 가리키게 바뀐다. 다음 호출부터는 어느 노드에서 시작하든 한 번에 루트에 닿는다.

// 경로 압축 버전
int find(int x){
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]); // 돌아오면서 parent[x]를 루트로 갱신
}

이 덕분에 find 의 시간복잡도는 사실상 $O(\alpha(V))$ 까지 내려간다. $\alpha$ 는 아커만 함수의 역함수로, 현실적인 입력 크기에서는 5를 넘지 않는다. 거의 $O(1)$로 봐도 무방하다.

💡 C++ 발견 2 — Lambda를 이용한 인라인 정렬

간선을 가중치 오름차순으로 정렬할 때, 굳이 별도 비교 함수를 뺄 필요 없이 std::sort 내부에서 람다를 바로 쓸 수 있었다.

sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
    return a.weight < b.weight;
});

코드의 응집도가 확 올라간다.

설계 포인트

전역 배열 활용: parent 배열을 전역으로 선언해 함수 간 참조 전달 없이 바로 접근할 수 있게 했다.
unite 함수 설계: 루트가 다를 때만 병합하고 true 를 반환하도록 해서 메인 루프를 간결하게 유지했다.

최종 코드

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

struct Edge {
    int u, v, weight;
};

int parent[10005];

int find(int x){
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

bool unite(int u, int v){
    int rootU = find(u);
    int rootV = find(v);

    if(rootU != rootV){
        parent[rootU] = rootV;  // rootV의 부모가 아닌 rootV 자체를 가리켜야 함
        return true;
    }
    return false;
}

int main()
{
    int V, E;
    cin >> V >> E;

    vector<Edge> edges;

    for(int i = 0; i < E; i++){
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    sort(edges.begin(), edges.end(), [] (const Edge &a, const Edge &b){
        return a.weight < b.weight;
    });

    for(int i = 1; i <= V; i++) parent[i] = i;

    int totalWeight = 0;
    int edgeUsed = 0;

    for(const auto& edge : edges){
        if(unite(edge.v, edge.u)){
            totalWeight += edge.weight;
            edgeUsed++;
            if(edgeUsed == V - 1) break;
        }
    }

    cout << totalWeight;

    return 0;
}

7. 마치며

"이 알고리즘을 써서 맞았다"에서 끝내지 않고, 대입 연산의 반환값이나 전역/지역 변수의 메모리 차이 같은 언어 동작 원리까지 파고들 수 있어서 유익한 문제였다. 제한된 시간 속에서도 개념을 하나씩 연결해 나가는 과정 자체가 재밌다.