[Baekjoon] 백준 1753 최단경로 (G4^ / 다익스트라) - Python

링크

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

1753번: 최단경로

 

 

 

 

문제 해석

정점의 개수와 간선이 개수가 주어짐

각 간선은 가중치를 가짐

 

시작 정점이 주어졌을 때, 시작 정점으로부터 다른 정점으로 가는 최단거리를 각각 출력하기

 

 

 

 

풀이 & 코드 해석

다익스트라의 기본이 되는 문제입니다.

 

다익스트라 알고리즘에 맞춰서 풀면 쉽게 해결됩니다.

 

 

 

 

코드

import heapq

v, e = map(int, input().split())

k = int(input())

graph = [[] for i in range(v + 1)]
distance = [int(1e9)] * (v + 1)

for i in range(e):
    u, v, w = map(int, input().split())
    graph[u].append([v, w])

q = []

# 파이썬 우선 순위 큐
# heapq : 최소 힙
# heapq.heappush(배열, 값) # 만약 값을 (1, 2), [99, 1] 형태로 넣으면 첫 번째 요소 기준으로 정렬
# heapq.heappop(배열)

# 시작 정점을 우선 순위 큐에 넣음 (우선 순위 큐의 정렬 기준은 거리가 짧은 순)
heapq.heappush(q, (0, k))
distance[k] = 0 # 시작점은 0으로 초기화 필요

while q:
    dist_now, node_now = heapq.heappop(q)

    # 이번에 큐에서 빠진 거리와 현재 거리 배열에 저장된 거리가 다르면 무시
    # 최단거리가 이미 업데이트 된 경우 무시
    if dist_now != distance[node_now]:
        continue

    # 현재 탐색 중인 노드와 연결된 모든 노드를 확인
    for u, weight in graph[node_now]:
        # 비교 대상까지 현재 저장 중인 최소 거리 > 시작점부터 나까지 걸린 거리 + 나에서 비교 대상까지 거리
        if distance[u] > distance[node_now] + weight:
            distance[u] = distance[node_now] + weight
            # 거리가 업데이트 되었다면 업데이트 한 노드를 우선 순위 큐에 추가
            heapq.heappush(q, (distance[u], u))

for i in range(1, len(distance)):
    if distance[i] == int(1e9):
        print("INF")
    else:
        print(distance[i])

 

 

 

 

발생한 문제 & 해결 방안

python에서는 우선 순위 큐를 사용하기 위해서 heapq를 이용한다.

 

기본적인 다익스트라 알고리즘 코드 작성법을 상기하는 것이 중요하다.

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java