[BOJ] 11404번 | 플로이드 (Python3)

🔗문제 보러가기

11404번: 플로이드

 

 

문제 설명

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

 

---

입력

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

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

 

---

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

 

---

예제 입출력

 

---

풀이 전략

시작 도시 A  →  도착 도시 B로 가는 노선이 여러 개일 수도 있다는 부분을 못 봐서 틀렸었네요.
Floyd-Warshall 알고리즘을 쓰는 문제더군요. 학교 알고리즘 수업 시간에 한 번 들었던 것 같은데 기억이 안 나서 다시 살펴봤었습니다. 잘 정리해놓으신 글이 있어서 다행이었습니다.

제 풀이과정 순서는 다음과 같습니다.

• 굉장히 큰 수로 이루어진 n X n 2차원 리스트를 생성
• A도시에서 B도시로 가는 비용을 2차원 리스트에 입력 받기
  • A도시에서 B도시로 가는 노선은 여러 개가 있을 수 있으므로, 그 중 가장 적은 비용을 선택
• 플로이드 알고리즘 동작
  • 자기 자신에게 가는 노선은 없다고 했으므로 0 처리
  • 기존 노선 비용과 경유지로 돌아가는 노선 비용 중 작은 것을 선택
• 계산된 결과값을 바탕으로 출력
  • 갈 수 없는 도시의 경우(즉, 초기값 그대로라면) 0 출력
  • 아니라면 계산했던 최소 비용 출력

 

---

소스 코드 및 결과

import sys
input = sys.stdin.readline

n = int(input())          # 도시의 개수 (2이상 100 이하)
m = int(input())          # 버스 개수 (1 이상 100,000 이하)
costTable = [[sys.maxsize] * n for _ in range(n)]  # 2차원 리스트 만들기

for _ in range(m):        # 시작 도시에서 도착 도시로 가는 여러 노선 중 가장 작은 비용 노선 선택
    startCity, aliveCity, cost = map(int, input().split())
    costTable[startCity - 1][aliveCity - 1] = min(costTable[startCity - 1][aliveCity - 1], cost)

for wayPoint in range(n):
    costTable[wayPoint][wayPoint] = 0   # 자기 자신에게 가는 노선은 없으므로 0 처리
    
    for startCity in range(n):
        for aliveCity in range(n):
            originalRouteCost = costTable[startCity][aliveCity]
            wayPointRouteCost = costTable[startCity][wayPoint] + costTable[wayPoint][aliveCity]
            costTable[startCity][aliveCity] = min(originalRouteCost, wayPointRouteCost)

for costs in costTable:
    for cost in costs:
        if cost == sys.maxsize:
            print(0, end = ' ')
        else:
            print(cost, end = ' ')
    print()

 

sys.stdin.readlin을 처음 써봤네요. 이게 더 입력 받는 속도가 빠르다고 하더군요.