[ Baekjoon : python ] 백준 11404번 플로이드 - 플로이드 워셜 알고리즘 (Floyd WarshAlgorithm)

[  BAEKJOON ONLINE JUDGE  ] 11404 플로이드 _ Python 파이썬

 

1. 문제

 

 

입력 예시	출력 예시
5 14 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 3 5 10 3 1 8 1 4 2 5 1 7 3 4 2 5 2 4	0 2 3 1 4  12 0 15 2 5 8 5 0 1 1 10 7 13 0 3 7 4 10 6 0

www.acmicpc.net/problem/11404 

11404번: 플로이드

---

 

2. 아이디어

 

이 문제는 플로이드 워셜 알고리즘을 이용한 가장 기초 문제이다.

이에 대한 개념은 아래 게시글에 정리해두었다.

 

플로이드 워셜 개념

codingexplore.tistory.com/53

[ 알고리즘 개념 ] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드 워셜 구현

codingexplore.tistory.com/54

[ 알고리즘 개념 ] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 구현 - 파이썬(Python)

 

---

3. 코드

 

위 정리 게시글의 코드 그대로 사용하면 당연히 틀린다.

 

틀리는 원인 1. 문제조건 "만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다." 를 무시했을 경우

 

틀리는 원인 2. 그래프 초기화 실수

- 입력 예시를 보면 이 문제에서는 A->B 로 갈 수 있는 여러 간선이 존재할 수 있다.

 

- 따라서 초기화 시 입력받은걸 무조건 할당하면 안된다.

- 19~20 라인의 코드를 보면, 현재 dist 값보다 더 작을 경우에만 새로 갱신하여 초기화한다.

 

# 플로이드
import sys
input = sys.stdin.readline
INF = int(1e9)
 
n = int(input()) # 노드의 개수
m = int(input()) # 간선의 개수
 
graph = [[INF] * (n + 1) for _ in range(n + 1)] # 최단거리 테이블
 
for s in range(1, n + 1):
    for e in range(1, n + 1):
        if s == e: # 그래프의 시작지점 == 도착지점
            graph[s][e] = 0 # 거리 0으로 초기화
 
# S0 : 그래프 초기화
for _ in range(m):
    s, e, dist = map(int, input().split())
    if graph[s][e] > dist:
        graph[s][e] = dist
 
# S1 ~ SN : 모든 노드를 돌며 각 노드를 거치는 모든 경로 검토
for node in range(1, n + 1): # 노드에 대한 루프
    for s in range(1, n + 1): # 2차원 그래프 루프
        for e in range(1, n + 1):
            graph[s][e] = min(graph[s][e], graph[s][node] + graph[node][e])
 
# 출력
for s in range(1, n + 1):
    for e in range(1, n + 1):
        if graph[s][e] == INF:
            print("0", end = ' ')
        else:
            print(graph[s][e], end = ' ')
    print()