[백준 11403번] 경로 찾기 -python

문제 링크

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

11403번: 경로 찾기

풀이

- 플로이드 워셜 알고리즘을 사용하여 풀 수 있는 문제이다. 

: 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용할 수 있는 알고리즘으로, 

점화식 D(a,b) = min(D(a,b), D(a,k) + D(k,b)) 

- 해당 문제에서는 

graph[a][b] 가 1이거나, graph[a][k] 와 graph[k][b]가 모두 1이면 a에서 b로 가는 경로가 있음을 의미한다. 

n = int(input())

graph = []

for _ in range(n):
  graph.append(list(map(int,input().split())))

for k in range(n):
  for i in range(n):
    for j in range(n):
      if graph[i][j] ==1 or (graph[i][k] == 1 and graph[k][j]):
        graph[i][j] = 1 

for a in graph:
  for b in a:
    print(b, end = " ")
  print()