[백준] 11403번 경로 찾기 해설 및 풀이 (Python)

백준 11403번 경로 찾기

https://www.acmicpc.net/problem/11403

---

문제 유형

그래프 이론 그래프 탐색 최단 경로 플로이드–워셜

 

풀이 방법 도출

1. 정점 수 N과 N x N 인접 행렬이 주어진다.
2. i에서 j로 길이가 양수인 경로가 존재하는지 구합니다.
3. 플로이드-워셜 알고리즘을 사용하여 모든 정점 쌍 (i, j)에 대해 도달 가능한지 판단합니다.
4. 만약 i → k 그리고 k → j가 가능하면 i → j도 가능하므로, graph[i][j] = 1로 갱신합니다.
5. 모든 노드 쌍에 대해 반복합니다.
6. 도달 가능한 경우 1, 불가능한 경우 0을 출력합니다.

 

 

시간 복잡도

• 3중 for문 : O(N³)

---

핵심 코드 삽입 및 설명

import sys
from typing import List

def floyd_warshall(graph: List[List[int]]) -> List[List[int]]:
    n = len(graph)
    # 모든 정점 쌍에 대해 중간 정점 k를 거쳐가는 경로 확인
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # i -> k 경로와 k -> j 경로가 모두 존재하면 i -> j 경로도 존재함
                if graph[i][k] and graph[k][j]:
                    graph[i][j] = 1
    return graph

def main():
    input = sys.stdin.readline
    n = int(input().strip())
    
    # 인접 행렬 입력 받기
    graph = [list(map(int, input().split())) for _ in range(n)]

    # 경로 존재 여부를 플로이드-워셜로 계산
    result = floyd_warshall(graph)

    # 결과 출력
    for row in result:
        print(' '.join(map(str, row)))

if __name__ == "__main__":
    main()