백준 - 11404번 플로이드 python 문제풀이 [Hellfer]

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

11404번: 플로이드

🔷 알고리즘 분류 - 플로이드-워셜, 난이도 - 골드 5

🔶문제 풀이 - 플로이드-워셜을 이용한 풀이

플로이드 워셜이란?

플로이드 워셜(Floyd-Warshall) 알고리즘은 그래프에서 모든 노드 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 '모든 노드'를 '중간에 거치는 노드'로 삼아 '모든 노드 쌍'에 대한 최단 경로를 계산합니다.

본질적으로 플로이드 워셜 알고리즘은 다이내믹 프로그래밍 기법을 사용합니다. 그래프의 각 노드를 순회하면서 그 노드를 거쳐가는 모든 노드 쌍에 대한 최단 거리를 갱신해 나갑니다. 이렇게 하면 각 노드를 거쳐가는 모든 경우를 고려하게 되므로, 결과적으로 모든 노드 간의 최단 거리를 구할 수 있습니다.

플로이드 워셜 알고리즘이 사용되는 경우는 주로 '모든 노드 간의 최단 경로'를 한 번에 알아야 하는 경우입니다. 그리고 이 알고리즘의 시간 복잡도는 O(N^3)입니다 (N은 노드의 개수). 따라서, 노드의 개수가 500개 이하인 경우에 주로 사용되는 편입니다.

단, 플로이드 워셜 알고리즘은 음의 사이클을 감지할 수 없으므로, 그래프에 음의 사이클이 존재하는 경우에는 사용할 수 없습니다.

 

플로이드 워셜 알고리즘에서 사용되는 점화식은 다음과 같습니다.

D_ab = min(D_ab, D_ak + D_kb)

여기서 D_ab는 노드 a에서 노드 b로 가는 최단 거리를 의미하며, D_ak는 노드 a에서 노드 k로 가는 최단 거리, D_kb는 노드 k에서 노드 b로 가는 최단 거리를 의미합니다.

이 점화식은 "a에서 b로 바로 가는 거리"와 "a에서 k를 거쳐 b로 가는 거리" 중 어떤 것이 더 짧은 지를 판단하는 것을 의미합니다. 만약 a에서 k를 거쳐 b로 가는 거리가 더 짧다면, a에서 b로 가는 최단 거리를 그 값으로 갱신합니다.

이 점화식을 통해 모든 노드를 거쳐보면서 최단 거리를 갱신해 나가는 것이 플로이드 워셜 알고리즘의 핵심입니다. 이 알고리즘은 모든 노드를 한 번에 거쳐보며 최단 경로를 찾는 방식으로, 각 노드를 거쳐가는 모든 경우를 고려하여 최단 경로를 찾습니다.

 

import sys
input = sys.stdin.readline
INF = int(1e9)

# 도시의 개수 n, 버스의 개수 m
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 = 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()

 

🔶 초보자를 위한 생각주머니 키우기

🔸문제요약

이 문제는 버스로 이동하는 모든 도시 쌍의 최소 비용을 구하는 문제입니다. 도시의 개수와 버스 노선 정보가 주어지며, 두 도시를 연결하는 버스 노선은 하나가 아닐 수 있습니다. 또한, 버스는 한 번 타면 그 도시에서 내릴 때까지 타고 있어야 합니다.

🔸해결전략

1. 먼저, 도시의 개수 n과 버스 노선 정보를 입력받습니다. 이때, 노선 정보는 시작 도시, 도착 도시, 그리고 그 노선의 비용으로 주어집니다.

2. 가장 먼저, 도시 간의 비용을 저장할 2차원 배열을 만듭니다. 이 배열은 초기에 모든 요소를 무한대로 설정하고, 자기 자신으로의 비용은 0으로 설정합니다.

3. 버스 노선 정보를 입력받으면서, 노선의 시작 도시와 도착 도시 위치의 비용을 노선의 비용으로 갱신합니다. 이때, 만약 이미 그 위치에 비용이 설정되어 있다면, 더 작은 비용으로 갱신합니다.

4. 플로이드 워셜 알고리즘을 수행하여 각 도시에서 다른 모든 도시로의 최소 비용을 구합니다. 이 알고리즘은 각 도시를 거쳐가는 모든 경우를 고려하여 최소 비용을 찾습니다.

5. 마지막으로, 모든 도시 쌍에 대하여 최소 비용을 출력합니다. 이때, 도달할 수 없는 경우는 0을 출력합니다.

이러한 전략을 통해 문제를 해결할 수 있습니다. 이 문제는 플로이드 워셜 알고리즘을 이해하고 적용할 수 있는지를 측정하는 문제로, 이 알고리즘을 잘 이해하고 있다면 쉽게 해결할 수 있습니다.

 

🤗파이팅입니다~ 여러분!!🤗