[Python] 경로 찾기 - 백준 (최단경로)

해당 글은 백준 11403번 문제 '경로 찾기'를 다룬다.

문제

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

11403번: 경로 찾기

 

설명

해당 문제는 최단 경로 찾기 알고리즘 중 플로이드-워셜 알고리즘을 통해 해결할 수 있다.

정점 i에서 정점 j로 가는 경로는 정점 i에서 정점 k로 가는 경로+정점 k에서 정점 j로 가는 경로와 같다.

이를 이용해서 정점 k를 거쳐서 가는 경로가 있다면 해당 경로의 graph의 값을 1로 변경시켜준다.

 

코드

n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

for k in range(n):
    for i in range(n):
        for j in range(n):
            if graph[i][k] and graph[k][j]:
                graph[i][j] = 1

for i in range(n):
    for j in range(n):
        print(graph[i][j], end=' ')
    print()