이번 문제는 플로이드-와샬 알고리즘을 사용하여 쉽게 해결하였다. 우선 각 정점에서 다른 정점까지 도착할 수 있을 경우에 1로 표시되고, 아닐 경우 0으로 표시되므로, 해당 정점까지 바로 가는 경로가 있거나 중간 정점이 존재할 경우에는 도착할 수 있는 경우가 되므로 1로 갱신해주었다.

• n을 입력받는다.
• 경로를 입력받을 리스트 path를 선언한다.
• path를 n번 반복하며 입력받는다.
• n번 반복하는 k에 대한 for문을 돌린다.
  -> n번 반복하는 i에 대한 for문을 돌린다.
  --> n번 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 path[i][j]가 1이거나, path[i][k]가 1이고 path[k][j]가 1인 경우,
  ----> path[i][j]를 1로 갱신한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> path[i]를 언팩킹하여 출력한다.

Code

n=int(input())
path=[]
for _ in range(n):
    path.append(list(map(int, input().split())))
for k in range(n):
    for i in range(n):
        for j in range(n):
            if path[i][j]==1 or (path[i][k]==1 and path[k][j]==1):
                path[i][j]=1
for i in range(n):
    print(*path[i])