플로이드 백준 11404번 최단경로

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

문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

전형적인 최단 경로 문제입니다. 다만 문제의 입력 조건에 따르면 시작 도시 A와 도착 도시 B를 연결하는 간선이 여러개 일 수 있습니다. 이럴때 비용이 가장 짧은 간선만 고려하면 됩니다.

기본적으로 최단경로를 구하는 문제에 있어서 다익스트라와 플로이드 워셜 알고리즘이 있는데 플로이드 워셜 알고리즘이 복잡도는 더 높으나 구현하기는 간단합니다. 도시의 개수는 100개 이하의 정수이므로 플로이드를 이용해서 문제를 진행합니다.

초기에 간선 정보를 입력 받을때 가장 짧은 간선 정보만 저장한 다음에 플로이드 워셜 알고리즘을 수행하여 결과를 출력하면 됩니다.

INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

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

#2차원 리스트(그래프 표현)을 만들고, 모든 값을 무한으로 초기화
graph = [[INF]*(n+1) for _ in range(n+1)]

#자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
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라고 설정
    a, b, c = map(int, input().split())
    #가장 짧은 간선 정보만 저장
    if c < graph[a][b]:
        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 a in range(1, n+1):
    for b in range(1, n+1):
        #도달할 수 없는 경우, 0을 출력
        if graph[a][b] == INF:
            print(0, end=' ')
        #도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end = ' ')
    print()

진짜 풀이 자체는 심플합니다. 2차원 배열에 0으로 초기화 한다음 각 간선에 대해서 정보를 입력 받을 때 최소값이 있다면 갱신을 해주고 플로이드 워셜 알고리즘을 전개를 해줍시다. a->b로 가는데 싼지 a->k->b로 가는게 싼지 여기서 k는 할 수 있는 겨우의 수를 다 뒤져봅니다.

그리고 마지막으로 결과를 출력합니다.

참고로 백준에서는 Python은 시간초과 뜨지만 PyPy는 통과과 됩니다. PyPy는 Python을 완벽하게 문법을 준수하면서 최대 13배 까지 빠른 언어입니다.