Warshall과 도달 가능성의 논리
허용 중간 정점을 늘리며 불리언 or·and로 모든 쌍의 연결을 계산합니다.
A에서 B로 갈 수 있고 B에서 C로 갈 수 있다면 A에서 C로 갈 수 있습니다. 목표는 이 논리를 표의 갱신식으로 만들고 자기 자신에 대한 경로 약속을 구분하는 것입니다. 그래프 행렬과 조건식을 복습하세요.
개념과 약속
도달 가능성은 비용이 아니라 참·거짓입니다. 중간 정점을 k까지 허용하면 i→j가 가능하려면 기존 경로가 있거나 i→k와 k→j가 둘 다 가능해야 합니다. 따라서 R[i][j] = R[i][j] or (R[i][k] and R[k][j])입니다. 가장 바깥 반복이 k여야 허용된 중간 정점의 단계라는 뜻을 유지합니다.
이 함수의 기본은 간선을 하나 이상 사용하는 경로입니다. 자기 자신으로 돌아오는 사이클이 없으면 대각선은 거짓일 수 있습니다. reflexive=True는 이동 0번의 자기 경로도 허용해 처음부터 대각선을 참으로 둡니다. 어떤 약속을 택했는지 결과 설명에 꼭 적습니다.
중간 정점으로 연결하는 두 부분 경로
직접 간선만 알려져 있다. 도달 가능성을 유지한다. 각 단계의 값과 전환 이유를 비교합니다.
자료구조·알고리즘 · 상태와 관계
중간 정점으로 연결하는 두 부분 경로
같은 부분 경로 연결도 가능 여부와 최소 비용의 연산은 다릅니다.
화살표는 직접 간선이 아닌 부분 경로입니다. 이전 중간 정점을 거친 여러 간선을 한 화살표로 축약할 수 있습니다. 불리언 가능 여부와 숫자 비용을 같은 표에 섞지 않습니다.
이 예의 조건
- 본문과 전체 도표의 예를 따라 초기 관계부터 C 허용까지 진행합니다.
관계도의 보충 설명
| 구분 | 전체 도표의 내용 |
|---|---|
| 설명·조건 | 같은 부분 경로를 연결해도 가능 여부와 최소 비용의 연산은 다릅니다. |
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| 초기 관계 직접 간선만 알려져 있다. |
|
|
| A 허용 A를 거쳐도 새 A→C 경로가 없다. |
|
|
| B 허용 두 참 관계를 연결한다. |
|
|
| C 허용 도달 가능성을 유지한다. |
|
|
중간 정점으로 연결하는 두 부분 경로
직접 간선만 알려져 있다. 도달 가능성을 유지한다. 각 단계의 값과 전환 이유를 비교합니다.
자료구조·알고리즘 · 상태와 관계
중간 정점으로 연결하는 두 부분 경로
같은 부분 경로 연결도 가능 여부와 최소 비용의 연산은 다릅니다.
화살표는 직접 간선이 아닌 부분 경로입니다. 이전 중간 정점을 거친 여러 간선을 한 화살표로 축약할 수 있습니다. 불리언 가능 여부와 숫자 비용을 같은 표에 섞지 않습니다.
이 예의 조건
- 본문과 전체 도표의 예를 따라 초기 관계부터 C 허용까지 진행합니다.
관계도의 보충 설명
| 구분 | 전체 도표의 내용 |
|---|---|
| 설명·조건 | 같은 부분 경로를 연결해도 가능 여부와 최소 비용의 연산은 다릅니다. |
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| 초기 관계 직접 간선만 알려져 있다. |
|
|
| A 허용 A를 거쳐도 새 A→C 경로가 없다. |
|
|
| B 허용 두 참 관계를 연결한다. |
|
|
| C 허용 도달 가능성을 유지한다. |
|
|
손으로 상태 추적하기
정점 순서 A,B,C, 간선 A→B, B→C입니다.
| 단계 | A→C | 이유 |
|---|---|---|
| 직접 간선만 | 거짓 | 직접 연결 없음 |
| A 경유 허용 | 거짓 | 변화 없음 |
| B 경유 허용 | 참 | A→B와 B→C가 참 |
| C 경유 허용 | 참 | 기존 경로 보존 |
사이클이 없는 이 그래프에서 기본 대각선은 모두 거짓입니다.
직접 실행하기
아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.
def square_size(matrix):
size = len(matrix)
if any(len(row) != size for row in matrix):
raise ValueError("square matrix required")
return size
def transitive_closure(adjacency, reflexive=False):
size = square_size(adjacency)
reach = [[bool(value) for value in row] for row in adjacency]
if reflexive:
for i in range(size):
reach[i][i] = True
for k in range(size):
for i in range(size):
for j in range(size):
reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
return reach
adjacency = [[0, 1, 0], [0, 0, 1], [0, 0, 0]]
for row in transitive_closure(adjacency):
print(row)
print("0회 이동 허용:")
for row in transitive_closure(adjacency, reflexive=True):
print(row)실행 결과:
[False, True, True]
[False, False, True]
[False, False, False]
0회 이동 허용:
[True, True, True]
[False, True, True]
[False, False, True]왜 맞고 언제 끝나는가
단계 k 전에는 앞선 중간 정점만 허용한 경로를 기록합니다. k를 쓰지 않는 경로는 기존 값에, k를 거치는 경로는 i→k와 k→j의 연결에 포함됩니다. or는 두 가능성을 합치고 and는 이어 붙이기의 양쪽을 요구합니다. 유한한 n³개의 갱신을 마치면 모든 중간 정점이 허용됩니다.
비용과 적용 범위
정점 n개에 시간 O(n³), 결과 행렬 공간 O(n²)입니다. 한 출발점의 도달 집합만 필요하면 DFS·BFS가 더 직접적일 수 있습니다. 이 함수는 정사각형 행렬을 요구하며 원본을 바꾸지 않습니다.
스스로 풀어 보기
- A→B와 B→A가 있으면 기본 모드의 A→A는 참인가요?
- 식의 and를 or로 바꾸면 A→B 하나만으로 A→C가 참이 될 수 있는 이유를 설명하세요.
힌트
- 길이 2인 사이클을 만듭니다.
- 경유점까지 가거나 경유점에서 출발할 수 있다는 한쪽 정보만으로 전체를 연결할 수 없습니다.
해설
- 참입니다. 이동 0번을 허용하지 않아도 양의 길이 경로로 돌아올 수 있습니다.
- i→k만 참이어도 갱신되어 연결되지 않은 끝점까지 잘못 퍼질 수 있습니다. 두 부분이 함께 있어야 한 경로입니다.
흔한 오해
대각선이 항상 참인 표와 사이클이 있을 때만 참인 표는 서로 다른 경로 정의입니다. 구현 오류 여부를 보기 전에 약속을 확인하세요.
복습과 다음 연결
다음 Floyd–Warshall은 같은 중간 정점 구조에서 or·and를 min·더하기로 바꿉니다.