BOJ 11403 - 경로 찾기

문제

백준 온라인 저지 - 11403번

풀이 과정

임의의 한 정점에서 다른 모든 정점까지의 도달 가능성을 판단하는 문제입니다.
다대다 관계의 도달 가능성이기 때문에 각각의 정점에서 DFS 를 수행하는 방법도 있지만
플로이드 와샬 을 사용해서 구할수도 있습니다.

코드

import sys

N = int(input())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]


def floyd():
    global graph

    for k in range(N):
        for u in range(N):
            for v in range(N):
                graph[u][v] = graph[u][v] or (graph[u][k] and graph[k][v])


def solution():
    floyd()

    for row in graph:
        print(*row)

solution()