백준 1753번: 최단경로 (Python)

접근

이전의 이분 그래프 문제와 풀이 과정이 비슷했다.

참고: 2021.04.14 - [코딩/백준 (Python)] - 백준 1707번: 이분 그래프 (Python)

백준 1707번: 이분 그래프 (Python)

비슷한 풀이에 거기에 가중치를 추가로 저장하여 각각의 정점들을 탐색하면서 가중치의 최소값으로 최신화 해주면서 탐색을 이어나가면 된다. 이런 식으로 그래프에서 최단 경로를 찾는 알고리즘을 다익스트라 알고리즘이라고 한다. 이 알고리즘은 최단경로를 찾는 알고리즘 중 하나이고, 자세한 설명은 아래 링크를 참고하면 된다.

다익스트라 알고리즘 참고 자료

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

추가적으로 위의 접근 방법으로 접근하되, 정점 별로 가중치가 가장 작은 점부터 계산해야 중복계산을 막을 수 있기 때문에 기존 bfs에서 썼던 리스트보다는 최소 heap을 이용하여야 시간 초과를 피할 수 있다.

코드

import sys
import heapq

v, e = map(int, sys.stdin.readline().split())
start = int(sys.stdin.readline())
lines = [[] for _ in range(v + 1)]
for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    lines[a].append([c, b])
visited = [float('inf') for _ in range(v + 1)]
visited[start] = 0
heap = []
heapq.heappush(heap, (0, start))


def Dijkstara():
    while heap:
        weight, now = heapq.heappop(heap)
        if visited[now] < weight:
            continue
        for w, n in lines[now]:
            nw = w + weight
            if nw < visited[n]:
                visited[n] = nw
                heapq.heappush(heap, (nw, n))


Dijkstara()
for i in range(1, v + 1):
    if visited[i] == float('inf'):
        print('INF')
    else:
        print(visited[i])

더 생각해 볼 것?

접근 방향은 괜찮았다. 경로에 가중치를 같이 묶어서 저장하는 것이나, 가중치가 작은 순으로 정렬하여 다음 탐색 순서를 정하는 것.. 방향은 좋았으나 계속 시간초과가 떴다. 다익스트라 알고리즘이 무엇인지 찾아보아도, 내가 생각한 것과 동일한 방향인데 어디서 시간을 줄일까 하다가 다른 분들의 풀이를 보았더니 heap을 이용하여 풀었다. 상황에 맞게 리스트 뿐만 아니라 여러가지 정렬 방법을 적시적소에 적용하는 공부가 좀 더 필요한 것 같다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!