[백준 11404번] 플로이드 (Python)

2024.03.25 - [CS/Algorithm] - [알고리즘 개념 정리] 플로이드 워셜 (Python)

플로이드 워셜을 학습한 뒤 풀은 플로이드 워셜을 활용하는 문제를 풀었다 🐥

 

문제 링크

[백준 11404번] 플로이드

 

문제 요약

도시들 사이의 최단 거리를 구하는 문제로, 도시 간 이동 비용을 최소화하는 것이 목표

 

첫번째 줄에 도시의 개수 n이 주어진다 (2 <= n <= 100)

두번째 줄에 버스의 개수 m이 주어진다 (1 <= m <= 100,000)

이어서 m개 만큼의 출발 도시, 도착 도시, 비용이 주어진다. (비용은 100,000 보다 작거나 같은 자연수)

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

 

모든 도시 쌍에 대하여 도시 A에서 B로 가는데 필요한 최소 비용을 출력한다.

만약 A에서 B로 갈 수 없는 경우 0을 출력한다.

출력 형식은 도시의 개수 n에 따라 n개의 줄에 걸쳐, 각 도시에서 다른 도시로 가는 최소 비용을 공백으로 구분해 출력한다.

 

접근 방법 정리

문제 이름부터 플로이드!

1. 주어지는 도시의 수, 버스의 수 받기

2. n * n 이차원 리스트로 INF로 초기화 (사실 비용이 100,000까지라서 10억 보다 작은 수로 했어도 될 것 같다)

3. 자기 자신 -> 자기 자신으로 가는 경우 0으로 초기화

4. 문제에서 제공되는 출발, 도착, 비용 초기화

    여기서 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 이 문제의 조건에 따라 들어오는 값 중 작은 값을 입력해줘야 함

5. 플로이드 워셜로 초기화 (기존의 비용과 k를 거쳐가는 비용 중 최소로 초기화)

6. 문제의 출력 형식에 맞게 출력

 

코드

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
INF = int(1e9)
arr = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            arr[i][j] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    arr[a][b] = min(arr[a][b], c)

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            arr[a][b] = min(arr[a][b], arr[a][k] + arr[k][b])

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if arr[i][j] == INF:
            print(0, end=" ")
        else:
            print(arr[i][j], end=" ")
    print()