백준 11403 경로 찾기

경로 찾기

문제는 백준에서 확인 할 수 있다.

✔ 접근방법

플루이드-워셜 알고리즘을 이용하여
연결 관계를 계산하는 문제

✔ 코드

import sys
from copy import deepcopy

def solution(arr):

    size = len(arr)

    visit = deepcopy(arr)

    for k in range(size):
        for i in range(size):
            for j in range(size):
                if visit[i][k] == visit[k][j] == 1:
                    visit[i][j] = 1
            
    for line in visit:
        for elem in line:
            print(str(elem) + " ", end="")
        else:
            print()

if __name__ == "__main__":
    N = int(input())
    
    arr = []
    for _ in range(N):
        arr.append(list(map(int, sys.stdin.readline().rstrip().split())))
    
    solution(arr)

☝ 팁

시간복잡도 : O(n^3)