1. 문제 설명

경로 찾기

2. 문제 분석

플로이드-워셜 알고리즘(시간 복잡도 $O(n^3)$을 통해 i번째 노드에서 j번째 노드로 가는 최단 경로를 구할 수 있다. 이 문제에서는 경로가 있다면 1, 없다면 0으로 표시하는데, 거리가 무한대면 경로가 없는 것으로 본다.

3. 나의 풀이

import sys

n = int(sys.stdin.readline().rstrip())
nodes = [[] for _ in range(n)]
INF = sys.maxsize

for i in range(n):
    nodes[i] += map(int, sys.stdin.readline().rstrip().split())
    for j in range(n):
        if nodes[i][j] == 0:
            nodes[i][j] = INF

for k in range(n):
    for i in range(n):
        for j in range(n):
            if nodes[i][j] > nodes[i][k] + nodes[k][j]:
                nodes[i][j] = nodes[i][k] + nodes[k][j]

for i in range(n):
    for j in range(n):
        if nodes[i][j] == INF: nodes[i][j] = 0
        else: nodes[i][j] = 1
# 거리가 무한이면 갈 수 없다는 뜻.

for i in range(n):
    print(*nodes[i], sep=' ')