백준 11403번 경로찾기

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

11403번: 경로 찾기

n의 케이스가 0< n <= 100이라서 플로이드와셜로 해결이 가능한 문제인 것 같아 플로이드와셜로 해결을 하였다.

 

import sys
input = sys.stdin.readline
INF = int(1e9)

# graph 생성
n = int(input())
graph = []
for _ in range(n):
    a_list = list(map(int,input().split()))
    graph.append(a_list)

# 0인 값에 INF값을 넣어줌
for i in range(n):
    for j in range(n):
        if graph[i][j] == 0:
            graph[i][j] = INF

# 위상 정렬을 실시
for k in range(n):
    for a in range(n):
        for b in range(n):
            if graph[a][b] >= (graph[a][k] + graph[k][b]):
                graph[a][b] = 1

# 갈 수 없는 경로(INF)를 다시 0으로 바꿔줌
for a in range(n):
    for b in range(n):
        if graph[a][b] > 1:
            graph[a][b] = 0

# 결과 출력
for a in range(n):
    result = map(str,graph[a])
    print(' '.join(result))