[백준(python)] 11404 플로이드

구준희·2024년 2월 25일

다익스트라 알고리즘 백준 파이썬 플로이드 워셜

알고리즘

목록 보기

30/31

📌 난이도, 유형

난이도 : 골드4
유형 : 그래프 이론, 최단경로, 플로이드
시간제한 : 1초
메모리제한 : 256MB

📌 문제설명

📌 입출력 예

📄 코드

플로이드-워셜 알고리즘

INF = int(1e9)

# 노드의 개수 및 간선의 개수 입력받기
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())
    graph[a][b] = min(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):
        if graph[a][b] == INF:
        	# 도달할 수 없는 경우에는 0 출력
            print(0, end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

다익스트라 알고리즘

import sys
import heapq

input = sys.stdin.readline
v = int(input().rstrip())
e = int(input().rstrip())
graph = [[] for _ in range(v + 1)]
INF = int(1e9)
for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))


def djikstra(start):
    queue = []
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    while queue:
        dist, now = heapq.heappop(queue)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(queue, (cost, i[0]))


for i in range(1, v + 1):
    distance = [INF] * (v + 1)
    djikstra(i)
    for j in range(1, v + 1):
        if distance[j] == INF:
            print(0, end=" ")
        else:
            print(distance[j], end=" ")
    print()