경기를 다 안 치렀는데, 순위를 정할 수 있을까?
동네 팔씨름 대회를 떠올려봅시다. 선수들의 실력에는 분명한 서열이 있어서, 강한 선수는 약한 선수를 항상 이깁니다. 그런데 시간이 부족해 모든 선수가 다 붙어보지는 못했고, 일부 경기 결과만 기록됐어요.
다행히 단서가 하나 있습니다. "A가 B를 이기고, B가 C를 이겼다"면 — A는 C와 안 붙어봤어도 A가 C를 이긴다고 확신할 수 있습니다. 실력 서열이 일관되니까요.
예: 선수 5명, 기록된 경기는 P1>P2, P1>P3, P2>P4, P3>P4, P4>P5. 순위가 확정되는 선수는 3명. (P1·P4·P5는 확정, P2·P3는 서로 안 붙어 미확정)
문제는 이겁니다. 기록된 경기만으로, 나머지 모든 선수와의 승패가 전부 결정돼 순위가 정확히 정해지는 선수가 몇 명일까요?
왜 플로이드-워셜일까? (핵심 아이디어)
"A→B→C 면 A→C" 라는 규칙, 어디서 본 것 같지 않나요? 바로 그래프의 도달성(reachability) 입니다. 경기 결과를 화살표로 보면(a→b = a가 b를 이김), "i가 j를 이기는가?"는 곧 "i에서 j로 가는 경로가 있는가?" 와 같은 질문이 됩니다.
우리는 모든 쌍에 대해 이 승패를 알아야 합니다. 그래서 모든 점에서 모든 점으로의 관계를 한 번에 채우는 도구 — 플로이드-워셜이 딱 맞습니다.
다만 한 가지만 바꿉니다. 보통 플로이드-워셜은 거리를 더하고 최솟값을 취하죠.
- •일반:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) - •여기선 논리 OR:
win[i][j] = win[i][j] OR (win[i][k] AND win[k][j])
해석하면 *"i가 k를 이기고, k가 j를 이기면, i도 j를 이긴다."* — 우리가 찾던 추이 규칙 그 자체죠. 이렇게 거리 행렬을 승패(도달) 행렬로 바꾸면, 플로이드-워셜이 곧 추이적 폐쇄(transitive closure) 계산기가 됩니다.
순위가 "확정"된다는 건?
행렬을 다 채운 뒤, 한 선수 i를 봅니다. 나머지 선수 j마다 win[i][j](내가 이김)나 win[j][i](내가 짐) 중 하나라도 1이면 그 상대와의 승패를 안다는 뜻입니다.
- •나머지 N-1명 전부와의 승패를 알면 → 그 선수의 자리는 유일하게 결정됩니다.
- •단 한 명이라도 양방향 모두 0이면(서로 안 붙었고 추이로도 안 이어짐) → 두 선수의 상대 순위를 정할 수 없어 미확정.
위 예시에서 P2와 P3가 바로 그 경우입니다. 둘 다 P4·P5를 이기고 P1에게 졌지만, 서로의 승패만은 알 수 없어 끝내 순위가 안 정해집니다.
직접 눈으로 확인하기
경기 결과가 행렬에 채워지고, 경유 선수 k를 하나씩 바꿔가며 win[i][k] && win[k][j] 로 새 승패가 켜지고, 마지막에 선수별로 "모두와 승패를 아는가?"를 집계하는 전 과정을 단계별 시각화로 준비했습니다. k·i·j와 decided 카운트의 변화까지 한눈에 보입니다.
이 "거리 대신 도달 관계를 채운다"는 발상은 친구 관계 추적, 선후 관계(위상) 판정, 부품 호환성 등 수많은 변형으로 등장합니다. 한 번 원리를 눈으로 익혀두면 어떤 옷을 입고 나와도 풀 수 있습니다.