백준 11404. 플로이드

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

11404번: 플로이드

 

코드

import sys
input = sys.stdin.readline

INF = int(1e9)

# 노드 간선 개수 입력 받기
n = int(input())
m = int(input())

# 2차원 리스트로 그래프 표현
graph = [[INF] * (n+1) for _ in range(n+1)]

for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

# 각 간선 정보로 그래프 업데이트
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = min(c, graph[a][b])  # 노선이 하나가 아닐 수 있음

# 점화식 구현 (k는 거쳐가는 노드)
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 a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == INF:
            print('0', end=' ')
        else:
            print(graph[a][b], end=' ')
    print()

 

플로이드 워셜(최단 경로 알고리즘)을 사용하는 문제였다.

 

이코테에서 배운 기본적인 플로이드 워셜 알고리즘을 그대로 가져가면서

문제의 조건인

'시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다'를 만족하기 위해

min 함수를 활용해 더 작은 노선을 저장해줬다.