[탐색/플로이드] 백준 11404 플로이드 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11404번: 플로이드

 

 

 

2. 문제 풀이

 플로이드 알고리즘을 이용해서 최단경로를 탐색하는 문제입니다.

 

2022.02.28 - [Algorithm] - [Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기

[Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기

 플로이드 - 와샬 알고리즘에 대한 설명은 위 링크에서 찾아보실 수 있습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
n = int(input())
m = int(input())
INF = 10000000
graph = [[INF]*n for _ in range(n)] # INF는 연결되지 않은 경로
for _ in range(m):
    a, b, c = map(int, input().split())
    # 시작도시와 도착도시를 연결하는 노선은 하나가 아닐 수 있음
    graph[a-1][b-1] = min(graph[a-1][b-1], c)

  N*N 크기의 인접행렬로 그래프 정보를 입력 받습니다. 주의하실 점은 INF는 최소 100,000 * 100 이상으로 해야하며(최대 비용이 100,000이고 총 100개의 노드가 있으므로) , 가장 최소의 비용으로 저장해야한다는 점입니다. (시작도시와 도착도시를 연결하는 노선은 하나가 아닐 수 있음)

 

 

#플로이드 와샬 알고리즘
def floyd(n, dist):
    # 최단 경로 리스트 초기화
    for via in range(n): #경유지
        for start in range(n): #출발지
            for end in range(n): #도착지
                # 자기 자신으로 오는 경로는 없음
                if start == end:
                    dist[start][end] = 0
                # 경유해서 가는 게 더 빠르다면, 최단거리를 갱신
                elif dist[start][end] > dist[start][via] + dist[via][end]:
                    dist[start][end] = dist[start][via] + dist[via][end]
    return dist

 플로이드 와샬 알고리즘을 그대로 적용해줍니다. 자기 자신으로 오는 경로는 0입니다.

 

 

res = floyd(n, graph)

#결과 출력
for row in res:
    for i in row:
        if i == INF:
            print(0, end=" ")
        else:
            print(i, end=" ")
    print()

 INF이면 0으로 출력하고, 아니면 비용을 출력해줍니다.