플로이드 워셜 코딩테스트: 경유지 순서와 도달 불가를 검증하기

플로이드 워셜 코딩테스트에서 세 중첩 반복의 바깥쪽 k는 새로 허용하는 경유 정점을 뜻합니다. 이 DP 단계가 유지되어야 경유지 없는 경로와 i→k→j 경로를 빠짐없이 비교할 수 있습니다. 도달 불가 상태를 더하기 전에 거르고, 음수 간선과 음수 사이클을 나눠 처리하는 구현 및 작은 그래프 검증법을 정리합니다. PracHub의 Shortest Distance in an Unweighted Adjacency-Matrix Graph는 풀이 연습 자료이며 특정 시험 문제를 보장하지 않습니다.

근거 범위. 공식 언어 문서는 라이브러리 동작의 근거입니다. 아래 불변식과 풀이의 정당성은 명시한 입력 계약에 따른 유도이며, 배열·그래프·시간축과 검산 코드는 이 글의 합성 교육 사례입니다. 후보자 보고나 특정 회사의 출제 형식은 사용하지 않았습니다.

DP 상태가 반복 순서를 설명한다 (DP state)

정점이 0..n-1일 때 dist[i][j]를 현재 알려진 최단 거리로 둡니다. 바깥 루프의 k를 처리하기 전에는 0..k-1 정점만 중간 경유지로 허용했다고 생각할 수 있습니다. 정점 k를 새로 허용하면 경로는 k를 거치지 않거나, i → k → j로 갈 수 있습니다. 따라서 점화식은 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])입니다.

k를 바깥 루프에 두는 이유는 이 DP 단계 의미를 유지하기 위해서입니다. 임의로 반복 순서를 바꾸면 어떤 경로 조합이 이미 계산됐는지 점화식과 맞지 않게 되어 정답 보장이 사라집니다. “어떤 3중 반복도 괜찮다”가 아니라 상태 정의가 루프 순서를 선택합니다.

초기화와 도달 불가 가드 (Initialization and INF)

간선이 없는 쌍은 INF, 자기 자신은 0, 직접 간선은 그 비용으로 초기화합니다. 같은 두 정점 사이에 간선이 여러 개면 최솟값을 보존합니다. 구현에서 INF에 다른 값을 더하기 전에 두 부분 경로 모두 유한한지 확인해야 합니다. C++이나 Java에서는 INF + 비용이 overflow할 수도 있고, 선택한 sentinel보다 큰 실제 비용이 존재하면 거리로 오인할 수 있습니다.

def floyd_warshall(n, edges):
    INF = float('inf')
    d = [[INF] * n for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    for u, v, w in edges:
        d[u][v] = min(d[u][v], w)
    for k in range(n):
        for i in range(n):
            if d[i][k] == INF:
                continue
            for j in range(n):
                if d[k][j] == INF:
                    continue
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    negative_cycle = any(d[v][v] < 0 for v in range(n))
    return d, negative_cycle

Python의 float('inf')는 큰 정수 sentinel overflow 문제를 피하지만, 거리 합과 입력 숫자 타입을 명확히 유지해야 합니다. C++에서는 유효한 최단 거리의 상한보다 크고, 자료형의 최댓값에는 여유가 있는 sentinel을 고릅니다. 예컨대 음수 사이클이 없는 그래프의 비음수 가중치가 최대 W라면 단순 경로 상한 (V-1)W를 먼저 계산하고, 두 부분 거리의 덧셈도 표현 범위 안에 있는지 확인합니다.

음수 간선은 허용해도 음수 사이클은 별도 처리 (Negative cycles)

음수 간선 하나가 있다고 알고리즘이 즉시 실패하는 것은 아닙니다. 음수 사이클이 없으면 반복 완결 후에도 최단 거리는 유한하게 정의될 수 있습니다. 반면 도달 가능한 음수 사이클이 있으면 그 사이클을 반복해 비용을 계속 낮출 수 있어 해당 쌍의 최단 거리는 유한값이 아닙니다. 완결 후 dist[v][v] < 0이면 정점 v에서 도달해 되돌아올 수 있는 음수 닫힌 경로가 있음을 나타냅니다. 특정 쌍 (i,j)의 답이 무한히 작아지는지 판정하려면 i에서 v로 가고 v에서 j로 갈 수 있는지도 확인해야 합니다.

다음 예시에서 0→1=4, 1→2=-2, 0→2=5이면 0→2 최단 거리는 2입니다. 정점 3은 고립되어 있으면 0→3은 계속 도달 불가입니다. 음수 간선은 경로를 개선하지만 도달 불가 상태를 임의의 큰 수와 합산해서는 안 됩니다.

경로 복원과 알고리즘 선택 (Path reconstruction)

거리만 필요하면 행렬만으로 충분합니다. 실제 경로를 복원하려면 next[i][j] 또는 predecessor 행렬을 초기화하고, i→k→j가 개선될 때 첫 이동 정보를 갱신합니다. 개선된 거리의 반복 갱신 규칙과 복원 규칙을 같은 단계에서 일치시켜야 합니다.

시간은 O(V^3), 공간은 O(V^2)입니다. 모든 정점 쌍의 거리가 필요하고 정점 수가 비교적 작거나 그래프가 조밀할 때 잘 맞습니다. 큰 희소 그래프에서 한 출발점의 거리만 원한다면 다익스트라(음수 간선이 없을 때), 음수 간선이 있는 단일 출발점이라면 Bellman-Ford를 검토하세요. 구체적 제약이 선택을 결정합니다.

테스트 기준: 단순 반복 대신 다른 오라클 (Oracle tests)

작은 무작위 그래프에서 음수 사이클이 없는 입력을 생성해 각 시작점의 Bellman-Ford 결과와 비교하면 독립적인 기준을 얻을 수 있습니다. 별도로 고립 정점, 간선이 없는 그래프, 자기 루프, 음수 간선이지만 사이클은 없는 그래프, 음수 사이클을 테스트합니다. 모든 정점을 거치는 작은 경로를 직접 열거하는 방식은 순환 그래프에서 위험하므로 단순 경로 기준 오라클이라면 반복 정점 정책을 분명히 해야 합니다.

이어서 연습할 최단 거리 문제 (Practice)

k를 바깥 루프로 둘 때 유지되는 단계 (Phase invariant)

D^(k)[i][j]를 정점 집합 {0,…,k}만 중간에 쓸 수 있는 최단거리로 정의하면 recurrence는 두 경우 중 작은 값입니다. 정점 k를 사용하지 않으면 D^(k-1)[i][j]이고, 사용하면 D^(k-1)[i][k] + D^(k-1)[k][j]입니다. 구현은 in-place 갱신이지만 d[i][k]와 d[k][j]는 경유지 k를 추가하기 전 단계의 값으로 충분합니다. 음수 사이클이 없으면 빈 경로 때문에 d[k][k]=0이므로 해당 반복에서 자기 자신을 여러 번 붙여 더 나쁜 경로를 만들지 않습니다. 음수 사이클이 있으면 이 전제 자체가 깨지고 대각 값이 음수가 됩니다.

반복 순서를 바꾼 코드가 어떤 작은 예제에서 통과했다고 해도 DP 불변식이 보장된 것은 아닙니다. 테스트는 구현을 반증할 수 있지만, recurrence가 왜 모든 경유 집합을 누적하는지는 정당화해야 합니다. 면접에서는 코드의 세 중첩문을 말하기 전에 k가 “이번 단계에서 새로 허용한 중간 정점”임을 먼저 설명하고, 뒤의 i,j가 출발과 도착을 순회한다고 짚으면 순서의 이유가 분명해집니다.

음수 사이클의 영향을 받는 쌍 (Affected pairs)

어떤 정점 v에서 d[v][v] < 0이면 음수 사이클을 확인한 것입니다. 그러나 전체 그래프에서 사이클이 있다는 이유로 모든 쌍이 무한히 작은 것은 아닙니다. 쌍 (i,j)가 영향받으려면 i에서 해당 사이클 정점 v까지 도달할 수 있고, 다시 v에서 j로 나갈 수 있어야 합니다. 행렬 계산이 끝난 뒤 d[i][v] < INF, d[v][j] < INF, d[v][v] < 0을 모두 확인해 해당 쌍의 상태를 분류할 수 있습니다. 사이클과 무관한 연결 성분의 최단 거리는 유한하게 남습니다.

간선 비용이 음수가 아니고 한 시작점만 필요하면 다익스트라를 먼저 검토하세요. 음수 간선이 있으면 벨만-포드, 모든 쌍의 거리가 필요하고 V가 작으면 플로이드 워셜이 후보입니다. 알고리즘 선택은 익숙한 이름이나 구현 편의보다 V, E, 질의 수, 가중치 부호와 메모리 제한으로 정당화합니다.

다음 연습에서 설명할 한 가지 (Next exercise)

오늘은 Shortest Distance in an Unweighted Adjacency-Matrix Graph를 풀면서 도달 불가 초기화를 확인한 뒤 경계 사례 하나와 시간·공간 복잡도를 소리 내어 설명해 보세요. Practice 자료는 연습을 위한 기록이며 실제 시험 문제를 예측하지 않습니다.

4개 정점으로 경유 순서를 따라가기 (Four-node trace)

정점이 0,1,2,3이고 간선이 0→1=4, 1→2=-2, 0→2=5라면 k=0 단계에서는 0을 중간 경유 정점으로 허용해도 개선 경로가 없습니다. k=1 단계에서 0→1→2 경로가 발견되어 거리가 4+(-2)=2로 개선됩니다. 이후 정점 3은 어떤 단계에서도 연결되지 않으므로 dist[0][3]은 계속 INF입니다. 이 표는 루프의 k가 “현재 어떤 중간 정점을 허용했나”를 나타낸다는 점을 보여 줍니다.

실제 경로를 복원하고 싶다면 각 쌍의 다음 정점을 기록하는 행렬을 사용합니다. 직접 간선 u→v가 있으면 next[u][v]=v로 시작하고, k를 거쳐 거리가 갱신되면 next[i][j]=next[i][k]로 바꿉니다. 복원 중 정점이 무한히 반복되지 않도록 음수 사이클이 없는 쌍에서만 경로를 만들고, 목적지에 도달할 때까지 이동 횟수 제한을 두어 구현 오류도 방어할 수 있습니다.

무엇을 언제 출력할지 정하기 (Output contract)

문제는 도달 불가를 -1, 0, 문자열 등으로 출력하도록 요구할 수 있습니다. 내부 계산의 INF 표현과 외부 출력 규약을 분리하세요. 대각선 dist[i][i]=0은 빈 경로 비용이며, 직접 자기 루프가 양수라면 빈 경로가 더 짧습니다. 음수 자기 루프는 음수 사이클의 즉시 증거입니다. 여러 직접 간선 중 최솟값을 초기화하는 이유도, 더 비싼 간선이 현재 최단 경로를 악화시키지 않도록 하기 위해서입니다.

그래프가 희소하고 정점 수가 크다면 O(V^3) 시간과 O(V^2) 행렬 저장이 제한을 넘을 수 있습니다. 최단 거리 질의가 한 출발점뿐인지 모든 쌍인지, 간선 가중치에 음수가 있는지, 메모리 제한이 얼마인지부터 확인해 알고리즘을 고릅니다.

Sources and Further Reading

• CP-Algorithms: Floyd–Warshall — 점화식, 중간 정점 순서, 도달 불가와 음수 사이클 설명.
• Stanford CS161: Dynamic Programming—Bellman-Ford and Floyd-Warshall — DP 관점에서 최단 경로 알고리즘을 정리한 강의 노트.
• CP-Algorithms: Bellman–Ford — 음수 사이클이 없는 작은 그래프에서 비교할 단일 출발점 비교 알고리즘.