[Python] 백준 / silver / 1446 : 지름길
문제 링크 : https://www.acmicpc.net/problem/1446
최단거리 문제고, 다익스트라 알고리즘을 적용해서 풀 수 있었다. 다익스트라 알고리즘은 외우고 있어서 괜찮은데 다익스트라를 어떻게 적용해야 할지 판단하는 것이 관건이었던 것 같다.
다익스트라는 기본적으로 그래프 구조에서 사용하는 알고리즘이기 때문에 노드와 간선이 필요하다. 그런데 이 문제에선 명확하게 노드가 뭔지 판단하기 애매했다. 시작 노드를 0, 도착 노드를 문제에서 준 D 로 설정하고, 1,2,3,4,...,D-1,D 를 모두 노드로 간주하는거다. Python heapq 를 활용한 다익스트라 알고리즘은 O(E logV) 이고, 이 문제에서 D는 최대 10,000 이기 때문에 그래도 된다.
파이썬 코드
import sys import heapq N, D = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(D+1)] for i in range(D): graph[i].append((i+1, 1)) for i in range(N): start, end, length = map(int, sys.stdin.readline().split()) if end > D: continue graph[start].append((end, length)) INF = 987654321 distance = [INF]*(D+1) distance[0] = 0 q = [] heapq.heappush(q, (0, 0)) while q: d, now = heapq.heappop(q) if distance[now] < d: continue for x in graph[now]: cost = d + x[1] if distance[x[0]] > cost: distance[x[0]] = cost heapq.heappush(q, (cost, x[0])) print(distance[D])
Author And Source
이 문제에 관하여([Python] 백준 / silver / 1446 : 지름길), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@heyksw/Python-백준-silver-1446-지름길저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)