[Python] 백준 11404번 : 플로이드

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

11404번: 플로이드

---

💡 문제 풀이

그래프 문제 중 플로이드-워샬 알고리즘 문제이다.

 

플로이드-워샬 알고리즘을 구현하면 된다.

입력값 중에 목적지가 같은 버스가 있어서 edge들을 입력받을 때 더 작은 값으로 최신화해야 한다.

✔️ 느낀 점

플로이드-워샬 알고리즘 자체는 어렵지 않지만 문제 조건인 "갈 수 없을 때 0으로 출력하라."와 "같은 목적지의 버스가 있음."을 놓쳐서 계속 틀려서 화가 났다 ^^. 문제를 잘 읽자

💻 코드

INF = int(1e9)

# 도시(vertex), 버스(edge) 입력받기
N = int(input())
M = int(input())

# 플로이드-워셜은 2차원 배열이 필요하다.
graph = [[INF] * (N+1) for _ in range(N+1)]
for i in range(1, N+1):
    graph[i][i] = 0
    
for _ in range(M):
    a, b, c = map(int, input().split())
    # 더 비용이 적다면 최신화
    graph[a][b] = min(graph[a][b], c)

for k in range(1, N+1):
    for a in range(1, N+1):
        for b in range(1, N+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
                
for x in range(1, N+1):
    for y in range(1, N+1):
        if graph[x][y] == INF: print(0, end=' ')
        else: print(graph[x][y], end=' ')
    print()