[탐색/다익스트라] 백준 1753 최단경로 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1753번: 최단경로

 

 

 

2. 문제 풀이

 시작점에서 다른 모든 노드로의 최단 거리를 구하는 문제입니다.

 

2022.03.22 - [Algorithm] - [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로

[Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로

 모든 쌍의 최단 거리가 아니라, 시작점으로부터의 최단 경로를 구하는 문제이므로 '다익스트라' 알고리즘을 사용합니다. 다익스트라 알고리즘은 그리디 알고리즘 기법으로, 주변 노드부터 탐색해서 찾은 최단 거리를 바탕으로 각 노드까지의 최단 경로를 계산할 수 있습니다.

 

 

 

3. 코드

import heapq  # 우선순위 큐 구현을 위함
import sys
input = sys.stdin.readline

# 입력
V, E = map(int, input().split())
K = int(input())  # 시작점

graph = [{} for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    try:
        graph[u][v] = max(graph[u][v], w)
    except:
        graph[u][v] = w

def dijkstra(graph, start):
    distances = {node: int(1e9) for node in range(1, V+1)}  # 처음 초기값은 무한대
    distances[start] = 0  # 시작 노드까지의 거리는 0
    queue = []
    heapq.heappush(queue, [distances[start], start])  # 시작 노드부터 탐색 시작

    while queue:  # queue에 남아있는 노드가 없을 때까지 탐색
        dist, node = heapq.heappop(queue)  # 탐색할 노드, 거리

        # 기존 최단거리보다 멀다면 무시
        if distances[node] < dist:
            continue

        # 노드와 연결된 인접노드 탐색
        for next_node, next_dist in graph[node].items():
            distance = dist + next_dist  # 인접노드까지의 거리
            if distance < distances[next_node]:  # 기존 거리 보다 짧으면 갱신
                distances[next_node] = distance
                heapq.heappush(queue, [distance, next_node])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입
    return distances

res = dijkstra(graph, K)
for i in res.values():
    if i == int(1e9):
        print('INF')
    else:
        print(i)

 맨 처음에는 딕셔너리로 Graph를 입력받아 다익스트라를 적용했습니다. 예제는 문제없으나, 아무래도 try - except문으로 처리한 부분에서 오류가 생긴 듯합니다.

 

 

import heapq  # 우선순위 큐 구현을 위함
import sys
input = sys.stdin.readline

# 입력
V, E = map(int, input().split())
K = int(input())  # 시작점

graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w)) # 도착지, 가중치


# 다익스트라 최적경로 탐색
def dijkstra(graph, start):
    distances = [int(1e9)] * (V+1)  # 처음 초기값은 무한대
    distances[start] = 0  # 시작 노드까지의 거리는 0
    queue = []
    heapq.heappush(queue, [distances[start], start])  # 시작 노드부터 탐색 시작

    while queue:  # queue에 남아있는 노드가 없을 때까지 탐색
        dist, node = heapq.heappop(queue)  # 탐색할 노드, 거리

        # 기존 최단거리보다 멀다면 무시
        if distances[node] < dist:
            continue

        # 노드와 연결된 인접노드 탐색
        for next_node, next_dist in graph[node]:
            distance = dist + next_dist  # 인접노드까지의 거리
            if distance < distances[next_node]:  # 기존 거리 보다 짧으면 갱신
                distances[next_node] = distance
                heapq.heappush(queue, [distance, next_node])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입
    return distances

res = dijkstra(graph, K)
for i in range(1, V+1):
    print("INF" if res[i] == int(1e9) else res[i])

 graph를 리스트 형태로 바꾸어서 입력받았습니다. 리스트로 바꾸니, 무리 없이 통과했습니다.