🔗 문제 링크

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

💻 코드

N = int(input())

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

for k in range(N):
    for a in range(N):
        for b in range(N):
            if graph[a][k] == 1 and graph[k][b] == 1: 
                graph[a][b] = 1 

for a in range(N):
    for b in range(N):
        print(graph[a][b], end = " ")
    print()

설계

i에서 j로 가능 경로가 있는지 없는지 구해야 한다. i에서 다른 정점을 거쳐 j로 가는 경우를 고려하여 i에서 다른 정점에 갈 때 경로가 존재하고, 다른 정점에서 j로 갈 때 경로가 존재하면, i에서 j로 가는 경로가 존재한다.