[Python] BOJ/백준 11403번 경로 찾기

[문제]

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

11403번: 경로 찾기

 

[풀이]

그래프 최단 거리 문제

1. 다익스트라
   • 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
2. 플로이드 와샬
   • 거쳐가는 정점을 하나씩 다 설정을 하여 해당 정점을 기준으로 최단 거리를 구하도록 구성
     → 모든 쌍 간의 최단 거리를 구할 수 있음
   • 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘



 

 

[코드]

import sys

N = int(sys.stdin.readline())
graph = [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 graph[i][k] and graph[k][j]:
                graph[i][j] = 1

for i in range(N):
    for j in range(N):
        print(graph[i][j], end=" ")
    print()