2021.2.26 [백준] 경로 찾기

플로이드 워셜 알고리즘

 

 

Q

 

www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

A

 

입력받는 것이 고민이였다. 입력이 여러 개로 들어오고, 케이스마다 달라질 수 있기 때문에 다른 리스트로 입력받았더니 내가 그걸 해결하지 못했다. 그냥 graph.append로 그래프에 넣어주는게 제일 쉽다.

 

코드

 

INF = int(1e9)
n = int(input())
graph = []
for _ in range(n):

    graph.append(list(map(int, input().split()))) #입력을 그래프에 넣어주기

 

for i in range(n):
    for j in range(n):
        if graph[i][j] == 0: #0이 있으면 min 사용시 방해되기 때문에 INF로 값 바꿔주기
            graph[i][j] = INF
            
for k in range(n): #점화식 실행
    for i in range(n):
        for j in range(n):   
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(n):
    for j in range(n):
        if graph[i][j] > 0 and graph[i][j] != INF:
            print(1, end = ' ')
        else:
            print(0, end = ' ')
    print()