[BOJ] 11404번 플로이드 / 사용언어 : 파이썬(python)

※ 문제링크

11404번: 플로이드

※ 관련개념

플로이드-워셜(Floyd-Warshall) 알고리즘 이론과 파이썬 구현

해당문제는 플로이드 와샬 알고리즘을 활용하여 풀 수 있는 문제였다. 다익스트라 알고리즘으로도 동일한 결과를 산출하는 것이 가능했으나, 백준 테스트 결과 시간초과가 발생하여 플로이드 와샬 알고리즘에 대해 확인 후 코드를 구현하였다. 간단하게 설명하면 다익스트라 알고리즘이 특정 정점에서 다른 정점으로 가는 최단경로를 구하기 위해 모든 정점을 거쳐가는 경우를 그 때마다 호출하여최단경로를 구하는 반면, 플로이드 와샬 알고리즘은 정점에서 다른 모든 정점으로 가는 경우를 배열로 만든 후 한꺼번에 반복문을 통해확인하여 최단거리를 구하는 방법이라고 생각하면 된다. 자세한 풀이방법과 코드는 아래와 같다.

1. 각각의 정점에서 다른 정점을 경유하지 않았을 때의 최단경로를 저장할 배열을 만들고 값을 할당한다.

2. 반복문을 통해 특정 정점을 경유한다고 가정하였을때의 최단경로를 구한 후 기존 값보다 작으면 값을 바꾼다.

3. 반복문 완료 후 결과값을 출력하고 출력전 배열에 inf값을 0으로 환산(문제조건)해준다.

+ 시간 및 메모리 단축을 위해 sys를 사용하였습니다.

 

# 다익스트라 알고리즘 이용 - 시간초과
import heapq
import sys

# input = sys.stdin.readline
N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append([c, b])

def dijstra(start):
    heap = []
    heapq.heappush(heap, [0, start])
    dp = [float('inf') for _ in range(N+1)]
    dp[start] = 0

    while heap:
        wei, cp1 = heapq.heappop(heap)
        for line in graph[cp1]:
            wei_n, cp2 = map(int, line)
            if wei + wei_n < dp[cp2]:
                dp[cp2] = wei + wei_n
                heapq.heappush(heap, [wei + wei_n, cp2])

    for i in range(1, N+1):
        if dp[i] == float('inf'):
            dp[i] = 0

    print(*dp[1:])
    # return dp[1:]

# ans = []
for i in range(1, N+1):
    dijstra(i))
    # ans.append(dijstra(i))
    
# 플로이드-와샬 알고리즘

import sys

# input = sys.stdin.readline
N = int(input())
M = int(input())
graph = [[float('inf') for _ in range(N+1)] for _ in range(N+1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    if graph[a][b] > c:
        graph[a][b] = c

for i in range(1, N+1):
    graph[i][i] = 0

def Floyd_Warshall():
    for cp in range(1, N+1):
        for start in range(1, N+1):
            for end in range(1, N+1):
                if graph[start][end] > graph[start][cp] + graph[cp][end]:
                    graph[start][end] =  graph[start][cp] + graph[cp][end]

Floyd_Warshall()
for i in range(1, N+1):
    for k in range(1, N+1):
        if graph[i][k] == float('inf'):
            graph[i][k] = 0
            
for i in range(1, N+1):
    print(*graph[i][1:])

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.