[BOJ] 11403번 경로 찾기 / 사용언어 : 파이썬(python)

※ 문제링크 

11403번: 경로 찾기

※ 관련개념

플로이드-워셜(Floyd-Warshall) 알고리즘 이론과 파이썬 구현

해당 문제는 플로이드 와샬 알고리즘을 활용하여 풀 수 있는 문제였다. 가중치자체를 갱신하고 기록하지 않아도 되는 문제로 단순하게간선여부만 확인하면 되었기에 코드를 작성하는데 큰 어려움없이 풀 수 있었다. 자세한 문제풀이 방법과 코드는 아래와 같다.

1. 입력값을 바탕으로 2차원배열을 만든다. 

2. 3중 반복문을 통해 각각의 정점을 경유하여 특정 정점으로 갈 수 있는지를 확인하고 갱신한다.

3. 반복문이 종료된 이후 출력형식에 맞게 결과값을 출력해준다.

+ 시간 및 메모리 절감을 위해 sys를 사용하였습니다.

 

import sys

# input = sys.stdin.readline
N = int(input())
matrix = []
for _ in range(N):
    sample = list(map(int, input().split()))
    matrix.append(sample)

for cp in range(N):
    for i in range(N):
        for k in range(N):
            if matrix[i][k] == 0 and matrix[i][cp] + matrix[cp][k] == 2:
                matrix[i][k] = 1

for i in range(N):
    print(*matrix[i])

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.