[파이썬]백준 1753 최단경로

링크

백준 1753 최단경로

다익스트라를 구현하면 되는문제
알고리즘도 이해하고 있고 코드도 금방 짰는데 이상하게 계속 에러가 떠서 뭐지뭐지 하고 한참을 고쳤다..

문제점은 다익스트라 함수 마지막 즈음에 heappush할때 가중치로 누적합인 dis[v]를 넘겨줘야 했는데 w를 넘겨주고 있어서 틀린거였다. 진짜 찾고나니 어처구니가 없었다..

혼자 문제풀때도 그렇고 코딩테스트를 볼때마다 느끼는 건데 구현은 금방 해놓고 자잘한 실수때문에 시간을 엄청 잡아먹는다. 제발 꼼꼼하게 살피자.

통과하고 다른사람의 코드를 보다가 안게 있는데 이 문제의 경우 유향그래프이기 때문에 굳이 방문체크를 해줄 필요가 없다는 점이었다.

정답 코드

import sys; input = sys.stdin.readline
from heapq import heappush, heappop

def dijkstra(start):
    dis = [3000000] * (V + 1) # 거리 초기화
    visit = [0] * (V + 1) # 방문 초기화
    dis[start] = 0 # 시작노드까지 거리 0으로 초기화
    q = [[0 ,start]] # 시작노드 가중치, 시작 노드

    while q:
        k, u = heappop(q) # 현재정점까지의 거리, 현재 정점
        if visit[u]: continue # 현재 정점 방문 처음이면
        visit[u] = 1 # 방문처리
        for w, v in G[u]: # 현재 정점에서 인점 정점까지 거리 탐색
            # 인접정점 방문 안했고, 인접정점까지의 거리가 (현재정점까지 거리 + 인접정점으로 이동거리)보다 작으면
            if not visit[v] and dis[v] > dis[u] + w:
                dis[v] = dis[u] + w # 인접정점의 거리 = 현재 정점까지의 거리 + 인접 정점으로 이동거리
                heappush(q, [dis[v], v])
    return dis

V, E = map(int, input().split())
K = int(input())
G = [[] for _ in range(V + 1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    G[u].append([w, v]) # 유향그래프

ans = dijkstra(K)
for i in range(1, len(ans)):
    if ans[i] == 3000000:
        print('INF')
    else:
        print(ans[i])

알게된 것👨‍💻

• 다익스트라
• 유향그래프의 최단경로에선 굳이 방문처리를 할 필요 없다.