[python] 백준 - 1753. 최단경로

문제 해결

1. 방향이 있는 그래프에서 최단거리를 구하는 문제 | 보통 다익스트라 알고리즘을 사용한다.

2. 인접리스트, 가중치 배열, 힙큐를 준비한다.
 (1) 인접행렬보다 인접리스트가 조금 더 빠르다(?)

 (2) 가중치 배열: 인덱스 번호에 도착할 때의 가중치를 항상 최솟값으로 업데이트 해준다.

 (3) 힙큐는 항상 최솟값을 리턴해준다.

3. ex)a - c 와 a- c 로 갈 때의 가중치를 항상 비교하여 최솟값을 넣어줘야 한다.

 

-> selected배열(출발했었는지 확인)을 만들어서 했는데 어짜피 단방향이라 필요가 없었다.

python으로 제출 시 시간초과가 나서 pypy로 제출했더니 통과 했다.

python으로 통과한 사람과의 코드를 비교해봤는데 차이가없었다..... 후😭 왜때문인지 모르겠다.

 

 

소스 코드

import heapq
# 방향이 있는 그래프 이므로 selected(출발했었는지 확인)가 필요없다
V, E = map(int, input().split())
start = int(input())

# 인접리스트
adj = {i: [] for i in range(1, V+1)}
for _ in range(E):
    s, e, w = map(int, input().split())
    # 방향 그래프
    adj[s].append([e, w])

# dist: 부모인덱스에서 현재인덱스에 도달할 때 생기는 가중치를 담을 배열 | 항상 최소값을 넣어줄 것
INF = float('inf')
dist = [INF] * (V + 1)

# 힙큐는 항상 최솟값을 리턴해준다.
hq = []
heapq.heappush(hq, (0, start))
dist[start] = 0

while hq:
    # 힙큐에서 노드에 대한 가중치와 노드를 뽑는다.
    k, u = heapq.heappop(hq)

    # u에서 갈 수 있는 노드들을 뽑고 | u -> w
    for w, cost in adj[u]:
        # w 가 현재 가지고 있는 가중치보다 u에서 왔을 때의 가중치가 더 적다면
        # w: u에서 갈 수 있는 곳, cost: u -> w 의 가중치
        # dist[u], dist[w]: u, w까지 도달할 때 가중치
        # 내가 지금 w에 도달하는 가중치가, 다른 경로로 w에 도달하는 가중치보다 작다면
        if cost + dist[u] < dist[w]:
            # 가중치를 더 작은 것으로 업데이트, 힙큐에 저장
            dist[w] = cost + dist[u]
            heapq.heappush(hq, (dist[w], w))

# 결과 출력
for i in range(1, V+1):
    if dist[i] != INF:
        print(dist[i])
    else:
        print('INF')

 

출처 : BACKJOON ONLINE JUDGE

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

1753번: 최단경로