클라우드 Mac에서 Swift Union-Find 검증하기

오프라인 연락처 분류, 기기 간 연결 관계 관리, 이미지 군집화에서는 “두 객체가 같은 그룹에 속하는가”를 판단해야 할 때가 많습니다. 연결이 추가되기만 하고 삭제되지 않는다면, 매번 모든 관계를 순회하는 것보다 Union-Find(서로소 집합 자료구조)가 적합합니다. 반면 연결 경로를 설명해야 하거나 연결을 자주 되돌려야 한다면 원본 그래프를 유지하고 그래프 탐색이나 전용 동적 자료구조를 선택해야 합니다. 이 순수 Swift 로직을 클라우드 Mac의 빌드 전 검사에 넣으면 시간이 오래 걸리는 앱 빌드를 시작하기 전에 그룹 분류 오류를 발견할 수 있습니다.

입력과 관찰할 결과부터 정의하기

이 글에서는 무방향 연결을 사용하며, 노드 번호는 0..<n으로 고정합니다. 비즈니스 로직 계층에서 먼저 안정적인 식별자를 정수로 매핑해야 합니다. 배열에서 현재 화면에 표시되는 위치를 사용하면 목록 순서를 바꿀 때 객체의 정체성까지 달라지므로 사용해서는 안 됩니다. 매핑과 연결 데이터는 동일한 스냅샷에서 가져와야 합니다.

검증에서는 세 가지만 확인합니다. 두 노드가 연결되어 있는지, 연결 요소가 몇 개 남아 있는지, 특정 노드가 속한 연결 요소의 크기가 얼마인지입니다. 중복 연결이나 자기 루프 때문에 연결 요소 수가 줄어들어서는 안 됩니다. 원래 연결되어 있지 않던 두 그룹을 실제로 합쳤을 때만 개수가 하나 줄어야 합니다.

루트 노드는 구현 세부 사항이지, 비즈니스상의 그룹 식별자가 아닙니다. 같은 연결 집합이라도 입력 순서가 달라지면 대표 원소가 바뀔 수 있지만, 연결 관계는 반드시 같아야 합니다.

잘못된 인덱스는 데이터 가져오기 계층에서 거부하고 행 번호나 레코드 식별자를 기록해야 합니다. 아래 구현은 내부 제약을 사전 조건으로 명시합니다. 잘못된 입력을 조용히 무시하는 것을 오류 대응으로 간주하지 않습니다.

독립 실행 가능한 구현 작성하기

다음 내용을 union_find_check.swift로 저장합니다. 크기 기준 합치기는 작은 트리를 큰 트리 아래에 붙이고, 경로 압축은 조회 중 거친 노드가 루트를 직접 가리키도록 만듭니다. 크기 정보는 루트에서만 유효하므로 sizes의 임의 위치를 직접 읽어서는 안 됩니다.

struct UnionFind {
    private var parent: [Int]
    private var sizes: [Int]
    private(set) var components: Int

    init(_ count: Int) {
        precondition(count >= 0)
        parent = Array(0..<count)
        sizes = Array(repeating: 1, count: count)
        components = count
    }

    mutating func root(_ node: Int) -> Int {
        precondition(parent.indices.contains(node))
        var r = node
        while parent[r] != r {
            r = parent[r]
        }
        var current = node
        while parent[current] != current {
            let next = parent[current]
            parent[current] = r
            current = next
        }
        return r
    }

    @discardableResult
    mutating func union(_ a: Int, _ b: Int) -> Bool {
        var ra = root(a)
        var rb = root(b)
        guard ra != rb else { return false }
        if sizes[ra] < sizes[rb] {
            swap(&ra, &rb)
        }
        parent[rb] = ra
        sizes[ra] += sizes[rb]
        components -= 1
        return true
    }

    mutating func connected(_ a: Int, _ b: Int) -> Bool {
        let ra = root(a)
        let rb = root(b)
        return ra == rb
    }

    mutating func size(of node: Int) -> Int {
        let r = root(node)
        return sizes[r]
    }
}

조회 과정에서 경로를 수정하므로 메서드에 mutating을 지정합니다. 동일한 인스턴스를 여러 동시 실행 작업에 그대로 넘겨 수정하게 해서는 안 됩니다. 한 번의 그룹 계산을 단일 작업 안에서 처리한 뒤 불변 결과를 출력하는 방식이 가능합니다. actor로 감싸더라도 한 묶음의 연결 처리는 중간에 일시 중단 지점을 거치지 않는 연산 안에서 끝내야 합니다.

그래프 탐색으로 합치기 연산을 매번 교차 검증하기

예상 루트 번호 몇 개만 적어 두면 테스트와 구현이 같은 오류를 공유하기 쉽습니다. 더 신뢰할 수 있는 기준은 인접 리스트를 이용한 탐색입니다. 부모 포인터를 사용하지 않고 합치기 전략에도 의존하지 않기 때문입니다. 다음 코드를 같은 파일 끝에 추가합니다. 연결을 하나씩 추가하면서 모든 노드 쌍을 확인합니다.

func reachable(_ start: Int, in graph: [[Int]]) -> Set<Int> {
    var seen: Set<Int> = [start]
    var stack = [start]
    while let node = stack.popLast() {
        for next in graph[node] {
            if seen.insert(next).inserted {
                stack.append(next)
            }
        }
    }
    return seen
}

func verify(_ edges: [(Int, Int)], count: Int) {
    var uf = UnionFind(count)
    var graph = Array(repeating: [Int](), count: count)

    for (a, b) in edges {
        let expectedMerge = !reachable(a, in: graph).contains(b)
        precondition(uf.union(a, b) == expectedMerge)
        graph[a].append(b)
        graph[b].append(a)

        var unseen = Set(0..<count)
        var expectedComponents = 0
        for node in 0..<count {
            let group = reachable(node, in: graph)
            if unseen.contains(node) {
                expectedComponents += 1
                unseen.subtract(group)
            }
            precondition(uf.size(of: node) == group.count)
            for other in 0..<count {
                precondition(
                    uf.connected(node, other) == group.contains(other)
                )
            }
        }
        precondition(uf.components == expectedComponents)
    }
}

let edges = [(0, 1), (2, 3), (1, 2), (0, 3), (4, 4)]
verify(edges, count: 6)
verify(Array(edges.reversed()), count: 6)
precondition(UnionFind(0).components == 0)

이 예제는 서로 다른 그룹의 합치기, 중복 연결, 고립 노드, 자기 루프를 모두 다룹니다. 역순 실행은 중간 상태까지 같아야 한다는 뜻이 아닙니다. 각 단계의 결과가 그 시점의 그래프와 일치해야 한다는 뜻입니다. 최종 분할 결과도 입력 순서에 영향을 받지 않아야 합니다.

작은 데이터에서는 단계마다 전체를 대조하는 방식이 적합합니다. 큰 데이터를 다룰 때는 먼저 작은 그래프의 간선 부분집합을 전수 검사하고, 그다음 고정 시드를 사용한 샘플링을 수행합니다. 실패하면 전체 간선 순서를 저장해야 합니다. 난수 생성기나 생성 규칙도 바뀔 수 있으므로 시드만 저장해서는 안 됩니다.

빌드 전 검사에 연결하고 정확성과 성능 구분하기

먼저 실행 노드에 필요한 툴체인이 설치되어 있는지 확인한 뒤, 스크립트가 있는 디렉터리에서 실행합니다.

set -eu
xcrun swift --version
xcrun swift union_find_check.swift

스크립트가 정상 종료되면 검사를 통과한 것입니다. 사전 조건이 실패하면 0이 아닌 종료 상태를 반환합니다. 스크립트와 테스트 데이터를 저장소에 커밋하고, 파이프라인에서는 현지화된 출력을 파싱하는 대신 종료 상태를 직접 사용하도록 합니다. 사전 조건 검사를 제거하는 -Ounchecked로 이 검증 프로그램을 컴파일해서는 안 됩니다.

경로 압축을 별도로 검증하는 방법

연결 관계가 정확하다고 해서 경로 압축까지 제대로 작동한다고 볼 수는 없습니다. 테스트 전용 빌드에 읽기 전용 깊이 검사 기능을 추가할 수 있습니다. 먼저 여러 계층의 트리를 만들고 깊은 위치의 노드를 조회한 다음, 해당 노드가 루트를 직접 가리키는지 확인합니다. 테스트를 위해 쓰기 가능한 부모 배열을 비즈니스 인터페이스에 공개해서는 안 됩니다.

성능 검사는 별도의 큰 입력으로 수행하고, 최초 조회와 반복 조회를 나누어 기록합니다. 기준 구현인 전체 그래프 탐색은 측정 시간에 포함하지 않습니다. 또한 특정 클라우드 실행에서 얻은 밀리초 값을 모든 머신에 적용할 절대 임계값으로 삼아서는 안 됩니다. 부모 포인터 접근 횟수를 비교하는 편이 더 안정적인 검사 방법입니다.

실패 원인을 명확한 경계로 좁히기

연결 요소 수가 잘못되는 원인은 대개 중복 합치기에서도 개수를 하나 줄이는 데 있습니다. 연결 요소 크기가 과도하게 크다면 자기 루프와 중복 간선부터 확인합니다. 합친 뒤에도 일부 노드가 연결되지 않는다면 루트의 부모 포인터 대신 입력 노드의 부모 포인터를 잘못 수정했는지 살펴봅니다. 오류 유형마다 최소 간선 순서를 하나씩 남겨 두는 편이 대량의 비즈니스 데이터를 보관하는 것보다 회귀 테스트에 유리합니다.

입력 계층에서는 음수, 전체 노드 수와 같은 번호, 등록되지 않은 식별자를 별도로 테스트하여 자료구조에 들어오기 전에 거부되는지 확인합니다. 빈 집합에서는 노드를 조회할 수 없지만, 연결 요소 수는 정상적으로 0을 반환해야 합니다.

마지막으로 삭제 기능의 한계를 명확히 해야 합니다. 경로 압축은 원래 연결 형태를 없애므로 부모 포인터 하나를 바꾸는 것만으로 “관계 해제”를 구현할 수 없습니다. 연결 수가 많지 않다면 남은 간선으로 다시 구성하는 것이 가장 간단합니다. 롤백이 필요하다면 변경 로그를 사용하는 별도 설계를 채택하고 경로 압축 전략도 다시 검토해야 합니다. 검증 통과 기준은 유효한 입력에서 올바른 분할 결과를 얻고, 유효하지 않은 입력은 명확히 실패하며, 지원 범위를 벗어난 연산을 성공한 것처럼 처리하지 않는 것입니다.

자주 묻는 질문