코딩테스트 대비/BOJ
[Baekjoon/Python] 11403번: 경로 찾기 - 효과는 굉장했다!
bluetag_boy
2022. 2. 11. 04:32
반응형
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
알고리즘 분류
- 그래프 이론
- 그래프 탐색
- 플로이드-와샬
SOLUTION
import sys
N = int(sys.stdin.readline())
path = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
#플로이드-와샬 알고리즘
for k in range(N):
for i in range(N):
for j in range(N):
if path[i][k] and path[k][j]:
path[i][j] = 1
for row in path: # 행
for col in row: # 열
print(col, end = " ")
print()