클라우드 Mac에서 검증하는 iOS 최단 경로: 가중치, 도달 불가, 오버플로

오프라인 내비게이션, 캠퍼스 내 경로 안내, 앱 내부의 이동 흐름 설계에서는 iOS 클라이언트가 직접 최단 경로를 계산할 수 있습니다. 일반적인 예제에서는 거리를 올바르게 계산하더라도, 가중치가 0인 순환이나 연결되지 않은 정점, 매우 큰 가중치를 만나면 그럴듯하지만 잘못된 결과를 반환할 수 있습니다. 클라우드 Mac에 작고 명확한 Swift 참조 구현을 마련하면, 화면에서 경로를 눌러 보는 것만으로 확인할 때보다 알고리즘 회귀를 쉽게 찾아낼 수 있습니다.

그래프와 결과의 계약부터 정하기

이 글에서는 정점 번호가 0부터 시작하는 방향 그래프를 사용하며, 간선 가중치는 음수가 아닌 Int64입니다. 양방향 도로는 두 방향의 간선을 명시적으로 추가해야 합니다. 시작 정점에서 자기 자신까지의 거리는 0이고, 도달할 수 없는 정점에는 nil을 반환합니다. 0이나 최댓값 정수를 도달 불가 표시로 사용하면 안 됩니다.

입력을 받는 지점에서는 시작 정점, 간선의 도착 정점, 음수 가중치를 모두 검사해야 합니다. 시작 정점에서 도달할 수 없는 부분 그래프도 검사 대상입니다. 평행 간선은 허용하며, 알고리즘이 더 짧은 간선을 선택하도록 합니다. 자기 루프도 허용하지만, 그 때문에 갱신이 무한히 반복되어서는 안 됩니다.

Dijkstra 알고리즘은 가중치가 음수가 아니라는 전제에 의존합니다. 음수를 0으로 바꿔 입력을 “수정”하지 마세요. 그렇게 하면 업무에서 풀려던 문제 자체가 달라집니다.

미터나 밀리초 같은 정수 단위로 그래프를 구성한다면, 데이터를 변환하는 단계에서 정밀도를 정해야 합니다. 먼저 부동소수점으로 거리를 계산한 뒤 임시로 소수 부분을 버려 정수로 바꾸면, 테스트에서 비교하는 대상은 더 이상 동일한 그래프가 아닙니다.

검토하기 쉬운 참조 모델 작성하기

아래 구현은 정점을 하나씩 훑어 선택하며, 시간 복잡도는 O(V²＋E), 공간 복잡도는 O(V)입니다. 작은 그래프의 정확성을 검증하기 위한 모델이지, 운영 알고리즘이 대규모 지도에서 보이는 성능을 입증하기 위한 구현은 아닙니다. 코드를 shortest-path.swift로 저장하고, 이후의 테스트 사례도 같은 파일에 추가합니다.

enum GraphError: Error {
    case invalidVertex
    case negativeWeight
    case overflow
}

struct Edge {
    let to: Int
    let weight: Int64
}

func distances(
    _ graph: [[Edge]],
    from source: Int
) throws -> [Int64?] {
    guard graph.indices.contains(source) else {
        throw GraphError.invalidVertex
    }

    for edges in graph {
        for edge in edges {
            guard graph.indices.contains(edge.to) else {
                throw GraphError.invalidVertex
            }
            guard edge.weight >= 0 else {
                throw GraphError.negativeWeight
            }
        }
    }

    var result = Array<Int64?>(repeating: nil, count: graph.count)
    var settled = Array(repeating: false, count: graph.count)
    result[source] = 0

    for _ in graph.indices {
        var selected: Int?
        for vertex in graph.indices where !settled[vertex] {
            guard let value = result[vertex] else { continue }
            if let current = selected {
                if value < result[current]! {
                    selected = vertex
                }
            } else {
                selected = vertex
            }
        }

        guard let vertex = selected else { break }
        settled[vertex] = true
        let base = result[vertex]!

        for edge in graph[vertex] where !settled[edge.to] {
            let (candidate, overflow) =
                base.addingReportingOverflow(edge.weight)
            guard !overflow else { throw GraphError.overflow }

            if let previous = result[edge.to] {
                if candidate < previous {
                    result[edge.to] = candidate
                }
            } else {
                result[edge.to] = candidate
            }
        }
    }

    return result
}

이 모델은 거리만 반환하고 선행 정점은 관리하지 않습니다. 경로 복원 문제를 거리 검증에 섞지 않기 위해서입니다. 거리가 같은 정점은 번호순으로 처리하므로 결과를 재현하기 쉽지만, 업무 로직이 이 순서에 의존해서는 안 됩니다.

고정 테스트 사례로 경계 조건 확인하기

먼저 평행 간선, 가중치가 0인 순환, 고립 정점이 포함된 작은 그래프를 추가합니다. 기대 결과는 직접 명시하고, 다른 검증 대상 알고리즘을 호출해 정답을 생성하지 않습니다.

let graph: [[Edge]] = [
    [Edge(to: 1, weight: 9), Edge(to: 1, weight: 2)],
    [Edge(to: 2, weight: 0)],
    [Edge(to: 1, weight: 0), Edge(to: 3, weight: 3)],
    [],
    []
]

let actual = try distances(graph, from: 0)
precondition(actual == [0, 2, 2, 5, nil])

let singleton = try distances([[]], from: 0)
precondition(singleton == [0])

이어서 빈 그래프, 범위를 벗어난 시작 정점, 음수 가중치 간선, 범위를 벗어난 도착 정점, 유효한 최댓값 거리를 각각 추가합니다. 오류를 기대하는 각 사례에서는 구체적인 오류 타입을 개별적으로 검증해야 합니다. 아무 예외나 발생하면 통과한 것으로 처리해서는 안 됩니다.

let largest = try distances([
    [Edge(to: 1, weight: Int64.max)],
    []
], from: 0)
precondition(largest[1] == Int64.max)

do {
    _ = try distances([
        [Edge(to: 1, weight: Int64.max)],
        [Edge(to: 2, weight: 1)],
        []
    ], from: 0)
    preconditionFailure("Expected overflow")
} catch GraphError.overflow {
}

여기서는 보수적인 정책을 사용합니다. 실제로 수행한 완화 연산에서 오버플로가 발생하면 쿼리 전체를 실패로 처리하며, 그래프에 더 짧은 경로가 따로 있더라도 계산을 계속하지 않습니다. 운영 구현이 다른 정책을 사용한다면 계약을 별도로 정의해야 하며, 두 구현의 오류 동작을 그대로 비교해서는 안 됩니다.

몇 가지 정답뿐 아니라 성질도 검증하기

고정된 정답 외에도 세 가지 변환을 검증합니다. 각 정점의 간선 순서를 섞어도 거리는 바뀌지 않아야 합니다. 가중치가 더 큰 중복 간선을 추가해도 결과가 더 짧아져서는 안 됩니다. 원래 그래프와 연결되지 않은 유효한 부분 그래프를 추가해도 기존 정점의 결과는 그대로여야 합니다. 이러한 거리의 성질을 검증할 때는 관련된 모든 덧셈 결과가 표현 가능한 범위 안에 들도록 가중치 범위를 제한해야 합니다.

이런 성질 검증으로 입력 순서에 의존하거나 평행 간선을 잘못 덮어쓰는 등의 결함을 찾을 수 있습니다. 작은 무작위 그래프를 생성한다면 난수 시드를 고정하고, 실패 시 전체 인접 리스트, 시작 정점, 기대 결과를 저장해야 합니다. 재현하기 어려운 실패 번호 하나만 기록해서는 안 됩니다.

운영 인터페이스가 경로도 반환한다면, 간선을 하나씩 따라가며 추가로 검증해야 합니다. 시작점과 도착점이 올바른지, 모든 간선이 실제로 존재하는지, 가중치 합이 반환된 거리와 같은지 확인합니다. 평행 간선이 있다면 정점의 나열만 반환하기보다 간선 식별자를 반환하는 편이 좋습니다. 길이가 같은 최단 경로는 여러 개일 수 있으므로 특정 선행 정점 체인과 반드시 일치하도록 비교하지 않습니다.

클라우드 노드의 검증 진입점 연결하기

VMFly 물리 노드에서는 먼저 도구 체인을 기록한 뒤 컴파일하고 실행합니다. 다음 명령은 시뮬레이터에 의존하지 않으므로 전체 앱 빌드 전에 실행하기에 적합합니다.

set -eu
xcrun swiftc --version
mkdir -p .build
xcrun swiftc -Onone shortest-path.swift \
  -o .build/shortest-path-check
.build/shortest-path-check

예제에서는 잘못된 결과가 나오면 0이 아닌 종료 상태를 반환하도록 precondition을 사용합니다. 릴리스 최적화에서 제거될 수 있는 assert로 바꾸지 말고, 이 검사들을 삭제하는 -Ounchecked도 사용하지 마세요. 실제 프로젝트에서는 같은 테스트 사례들을 테스트 타깃에 연결하고, 운영용 경로 계산 진입점을 호출합니다.

파이프라인에는 최소한 실패한 그래프, 도구 체인 버전, 실제 거리 배열을 보관해야 합니다. 검증 순서는 입력 유효성, 거리 결과, 경로 재검증, 성능 예산 순으로 유지합니다. 정확성 검증 관문을 통과한 뒤 대규모 그래프의 실행 시간을 별도로 측정해야 합니다. 한 번 “빠르게 실행됐다”는 사실로 도달 불가 처리나 오버플로 의미론의 오류를 덮어서는 안 됩니다.

자주 묻는 질문