[플로이드 워셜] 백준 11403 경로 찾기

문제링크 www.acmicpc.net/problem/11403

 

 

 

[답코드]

import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정
 
n = int(input())
 
graph=[]
 
for _ in range(n):
    graph.append(list(map(int, input().split())))
 
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(n):
    for a in range(n):
        for b in range(n):
            if graph[a][k] and graph[k][b] :
                graph[a][b]=1
 
for i in graph:
    for j in i:
        print(j, end=" ")
    print()
 

 

 

[풀이법]

 기존 플로이드 워셜 알고리즘은 출발지 a, 도착지 b, 중간노드 k가 있을 때

a->b로 바로 가는 방법과 a->k->b 로 k를 거쳐 가는 방법 중 가장 거리가 작은 값을 선택하는 방법이었다.

 

 

 이번 11403 문제에서는 거리의 값이 중요한 게 아니라 '두 노드가 연결 될 수 있는지 아닌지' 가 중요하기 때문에 graph[a][k]가 연결 돼 있고 graph[k][b]가 연결 돼 있다면 graph[a][b]=1, 즉 a->b 노드로 갈 수 있다고 계속 저장해주면 된다.