11403번 경로찾기

실버 I

💡문제 분석 요약

floyd-warshall

플루이드-워셜

💡알고리즘 설계

플루이드 워셔로 모든 그래프로 갈 수 있는 가중치를 정리한다.

dist를 inf로 초기화 한다.

k를 거쳐서 i→j로 가는거와 i→j로 갈 수 있는 가중치 중 최솟값을 [i][j]에 넣는다.

이때, inf로 나온다는 건 i→j로 가는 경로가 없다는 뜻이므로 0으로 출력한다.. 그리고 inf가 아닌경우 경로가 있다는 뜻이므로 1로 출력한다.

💡코드

import sys
import math
input= sys.stdin.readline
n = int(input())
dist =[]

for i in range(n):
    a = input().strip().replace('0','inf')
    a = list(map(float,a.split(' ')))
    dist.append(a)

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
           #k를 거친 경로 vs i->j로 가는 직통 경로
for i in range(n):
    for j in range(n):
        if dist[i][j]==math.inf:
            print(0,end=' ')
        else:
            print(1,end=' ')
    print('')

💡 헷갈린 이유

오랜만에 플루이드워셜 알고리즘을 적용해서 어떻게 값이 들어왔는지 감이 잡히지 않았다.