백준 11403. 경로 찾기

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

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]

# 경유지 m을 통해 i -> j로 갈 수 있는지 확인
for m in range(n):
    for i in range(n):
        for j in range(n):
            # i->m, m->j로 갈 수 있으면 i->j로 갈 수 있다!
            if arr[i][m] == 1 and arr[m][j] == 1:
                arr[i][j] = 1

for a in arr:
    print(*a)

n이 100밖에 되지 않으므로 플로이드-워셜 알고리즘을 사용할 수 있었다!

최단 경로를 구하는 문제가 아니므로 dp 테이블을 따로 만들지 않아도 간단하게 해결 가능했다.