[BOJ] Q11403 경로 찾기

[BOJ] Q11403 경로 찾기

Question

Language: Python

Difficulty: Silver 1

방향 그래프가 주어졌을 때, 모든 경로를 찾는 ASSP 문제로 Floyd-Warshall 알고리즘을 이용하면 쉽게 풀이가 가능하다.

단, 주어진 조건에 따르면, 0은 길이 없고, 1은 길이 있는 것을 나태내니, 0을 inf로 변환해서 경로를 모두 찾은 다음 다시 inf을 0으로 바꿔주는 작업을 해야된다.

Solution

from math import inf
def distance_converter(option):
    if option:
        for i in range(n):
            for j in range(n):
                if graph[i][j]==0:
                    graph[i][j]=inf
    else:
        for i in range(n):
            for j in range(n):
                if graph[i][j]==inf:
                    graph[i][j]=0
                else:
                    graph[i][j]=1

def solution():

    distance_converter(True)

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j]=graph[i][k] + graph[k][j]

    distance_converter(False)

    for i in range(n):
        print(*graph[i])
    

if __name__ =="__main__":
    n=int(input())
    graph=[list(map(int,input().split())) for _ in range(n)]
    solution()