[백준] 11403번 경로 찾기(python)

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

11403번: 경로 찾기

 

1. 난이도 실버1 (🥈) 

 

2. 문제 해결 방법

플로이드 워셜 알고리즘을 이용하면 된다.

 

출발 -> 경유지까지 이어져 있고(True), 경유지->도착까지 이어져있으면(True)

 

출발-> 도착이 이어져있기 때문에 graph[출발][도착]에 1을 넣어주면 된다. 

 

3. 내가 작성한 코드

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][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()