백준 11403 <경로 찾기> Python

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

---

플로이드-워셜 알고리즘을 사용해 풀 수 있습니다.

시작 노드와 중간 노드가 연결되어있고, 중간 노드와 끝 노드가 연결되어 있으면 시작 노드와 끝 노드도 연결되어 있음을 알 수 있습니다.

---

import sys

input = sys.stdin.readline


def solution(N, mat):
    ## 플로이드-워셜
    # 중간 노드
    for c in range(N):
        # 시작 노드
        for f in range(N):
            # 끝 노드
            for b in range(N):
                # 시작 - 중간 / 중간 - 끝 이 이어져 있으면
                if mat[f][c] and mat[c][b]:
                    # 시작 - 끝도 이어져 있음
                    mat[f][b] = 1

    for i in mat:
        print(*i)


# 입력
N = int(input().strip())
mat = [list(map(int, input().strip().split())) for _ in range(N)]

solution(N, mat)