[백준] 11403번 - 경로 찾기 (python)

문제

가중치 없는 방향 그래프 G가 주어진다.

모든 정점에 대해 i → j로 가는 경로가 있는지 확인해, 모든 노드에서 모든 노드로의 경로 존재 여부를 출력하라.

 

문제 바로가기

11403번: 경로 찾기

 

풀이

• 모든 노드 → 모든 노드로의 최단 경로를 찾는데 사용되는 알고리즘인 플로이드-와샬 알고리즘을 사용했다. (DFS, BFS를 사용해서도 풀 수 있을 것 같다.)
• 이 문제에서는 자기 자신으로 가는 경로도 존재하는지 확인하는 점이 기존 플로이드-와샬 알고리즘과 다르다.
• a → k → b 노드 순서로 노드 k를 경유한다고 볼 때, a → k 경로가 존재하고 AND k → b 경로가 존재하면 a → b 경로도 존재한다고 볼 수 있다.

import sys
read = sys.stdin.readline

# 입력 받기
graph = []
N = int(read())
for i in range(N):
    graph.append(list(map(int, read().split())))

# 플로이드-와샬 알고리즘 사용
# a -> k -> b
for k in range(N):
    for a in range(N):
        for b in range(N):
            if graph[a][k] and graph[k][b]:
                graph[a][b] = 1

# 결과 출력
for i in range(N):
    print(*graph[i])

• 리스트 arr 대신 *arr 을 출력하면 콤마(,) 없이 숫자만 출력된다.