[Python] 백준 알고리즘 11404번 - 플로이드

[Python] 백준 알고리즘 11404번 - 플로이드

 

문제 출처 : https://www.acmicpc.net/problem/11404

11404번: 플로이드

P11404

 

 접근방식

플로이드 와샬 알고리즘을 활용하는 문제이다.

다익스트라 알고리즘이 하나의 노드를 기준으로 각 노드의 최소 가중치를 구하는 알고리즘이라면

플로이드 와샬 알고리즘의 경우에는 전체 노드끼리의 최소 가중치를 구하는 문제이다.

 

플로이드 와샬의 경우 삼중 반복문을 통해서 다익스트라 알고리즘에 비하면 간단하게 구현이 가능하다. 

 

다만 이번 문제에서는 조심해야하는점이 있다.

기존 플로이드 와샬의 문제를 살펴보면 출발점에서 도착점으로 가는 경우의 수가 하나인 경우가 대다수였지만

이번 문제의 경우에는 가중치가 여러개가 존재한다. 따라서 여러개가 주어진 가중치 중에서 최소값을 골라 그래프에 입력을 해줘야한다.

 

 

 구현 코드

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

# 주어진 도시(노드)와 버스 노선(간선)의 값
n = int(input())
m = int(input())

# 그래프를 만들기 위해 그래프를 생성, 도시의 번호를 맞추기위해 n+1번 반복
# 각각 도시, 방문 여부, 거리를 표현, 도시 끼리의 거리는 최대로 지정하고 시작
city = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신으로 돌아오는 경우의 거리를 0으로 초기화
for i in range(1, n + 1):
    for k in range(1, n + 1):
        if i == k:
            city[i][k] = 0

# 그래프 그리기
for _ in range(m):
    # a에서 b로 가는 비용이 c
    a, b, c = map(int, input().split())

    if city[a][b] != INF:
        city[a][b] = min(city[a][b], c)
    else:
        city[a][b] = c

# 플로이드 와샬로 그래프 체크
for j in range(1, n + 1):
    for i in range(1, n + 1):
        for k in range(1, n + 1):
            city[i][k] = min(city[i][k], city[i][j] + city[j][k])

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

 

 보충

• 다익스트라 알고리즘
• 플로이드와샬 알고리즘