유니온 파인드 (Disjoint Set Union)

유니온 파인드는 서로소 집합을 효율적으로 관리하기 위한 자료구조입니다. 각 집합을 트리 형태로 표현하며, 트리의 루트 노드가 해당 집합의 대표 원소가 됩니다.

핵심 연산

초기화 (Initialize): 각 원소를 자신을 루트로 하는 독립적인 집합으로 설정합니다.

type DisjointSet struct {
    root []int
    rank []int
}

func NewDisjointSet(size int) *DisjointSet {
    ds := &DisjointSet{
        root: make([]int, size),
        rank: make([]int, size),
    }
    for i := 0; i < size; i++ {
        ds.root[i] = i
        ds.rank[i] = 0
    }
    return ds
}

찾기 (Find): 원소가 속한 집합의 루트를 찾습니다. 경로 압축 최적화를 적용하여 탐색 경로상의 모든 노드를 루트에 직접 연결합니다.

func (ds *DisjointSet) Find(node int) int {
    if ds.root[node] != node {
        ds.root[node] = ds.Find(ds.root[node])
    }
    return ds.root[node]
}

합치기 (Union): 두 원소가 속한 집합을 병합합니다. 랭크 기반 합치기를 통해 트리의 높이를 최소화합니다.

func (ds *DisjointSet) Union(a, b int) bool {
    rootA := ds.Find(a)
    rootB := ds.Find(b)
    
    if rootA == rootB {
        return false
    }
    
    if ds.rank[rootA] > ds.rank[rootB] {
        ds.root[rootB] = rootA
    } else if ds.rank[rootA] < ds.rank[rootB] {
        ds.root[rootA] = rootB
    } else {
        ds.root[rootB] = rootA
        ds.rank[rootA]++
    }
    return true
}

활용 분야

• 무방향 그래프의 연결성 판별
• 사이클 검출
• 연결 요소 개수 산출

최소 신장 트리 (Minimum Spanning Tree)

최소 신장 트리는 그래프의 모든 정점을 연결하면서 간선 가중치의 합이 최소가 되는 트리입니다. 정점 수가 n개일 때 정확히 n-1개의 간선으로 구성되며, 사이클을 포함하지 않습니다.

크루스칼 알고리즘

크루스칼 알고리즘은 탐욕적 방법으로 최소 신장 트리를 구성합니다. 모든 간선을 가중치 기준 오름차순 정렬 후, 사이클을 형성하지 않는 간선부터 순차적으로 선택합니다.

실전 예제: 모든 점 연결하기

2차원 평면 상의 점들을 모두 연결하는 최소 비용을 구하는 문제입니다. 두 점 간 연결 비용은 맨해튼 거리로 정의됩니다.

func minCostConnectPoints(points [][]int) int {
    n := len(points)
    dsu := NewDisjointSet(n)
    
    // 모든 간선 생성
    type Edge struct {
        from, to, cost int
    }
    
    var edges []Edge
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            cost := abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1])
            edges = append(edges, Edge{i, j, cost})
        }
    }
    
    // 가중치 기준 정렬
    sort.Slice(edges, func(i, j int) bool {
        return edges[i].cost < edges[j].cost
    })
    
    // 크루스칼 알고리즘 적용
    totalCost := 0
    edgeCount := 0
    
    for _, e := range edges {
        if dsu.Union(e.from, e.to) {
            totalCost += e.cost
            edgeCount++
            if edgeCount == n-1 {
                break
            }
        }
    }
    
    return totalCost
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}