[백준/BOJ] 11403 - 경로 찾기

11403 - 경로 찾기

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

코드

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] == 1 and graph[k][j] == 1:
                graph[i][j] = 1

[print(*graph[i]) for i in range(len(graph))]

한마디

모든 정점에 대해 갈 수 있는 경로인지 아닌지를 확인하는 문제이므로 플로이드-와샬 알고리즘을 이용해 간단하게 풀 수 있었다.

11403번: 경로 찾기