[실버 I] 1446번. 지름길

 문제 

https://www.acmicpc.net/problem/1446

1446번: 지름길

 사용 언어 

Python3

 풀이 과정 

엘리스 강의로 다익스트라 알고리즘 개념과 우선순위 큐의 기본에 대해 공부하고 풀어보려고 했는데, 역시 바로 적용하는건 무리무리😌

심지어 적용한 코드를 보고도 잘 이해가 되지 않았다😅

 

나는 처음에 지름길로 언급된 위치만 정점으로 계산하려고 set을 사용해서 위치를 정의했는데,

그렇게 하면 이전 길들중 더 짧은 길을 파악하기가 어려워서 결국 0, 1, 2 ... D-1, D를 모두 정점으로 for문을 돌려 풀었다.

 

혼자 고민한 시간이 좀 길었지만 맞았습니다!!

다익스트라 알고리즘과 heapq를 사용한 방식은 시간은 같았지만 오히려 메모리 사용이 늘어났고 다른 사람들의 블로그를 봐도 이 문제는 heapq 사용 없이 최단거리를 찾을 수 있다고 설명했다.

 제출 답안 

from sys import stdin
input = stdin.readline

shortcutCount, highwayLong = map(int, input().split())
shortcutInfo = []
for _ in range(shortcutCount):
    start, end, cost = map(int, input().split())
    # 고속도로 역주행 불가: '도착위치 > 고속도로 길이'면 쓸데없는 정보
    if end > highwayLong:
        continue
    # 지름길 효율: '도착위치 - 시작위치 - 지름길 길이 = 음수'면 쓸데없는 정보
    if end - start - cost < 0:
        continue
    shortcutInfo.append((start, end, cost))

fastest = [i for i in range(highwayLong + 1)]
for j in range(highwayLong + 1):
    fastest[j] = min(fastest[j], fastest[j-1] + 1)
    for s, e, c in shortcutInfo:
        if j == s and fastest[j] + c < fastest[e]:
            fastest[e] = fastest[j] + c

print(fastest[highwayLong])

 다른 사람 코드 

그래도 처음으로 푼 다익스트라 알고리즘 문제이기 때문에 heapq까지 적용해서 푼 코드를 찾아보았다.

# 운전할 거리의 최솟값 구하기
import heapq
from sys import stdin
input = stdin.readline

shortcutCount, highwayLong = map(int, input().split())
# graph 2차원 리스트 선언
graph = [[] for _ in range(highwayLong+1)]
for i in range(highwayLong):
    graph[i].append((i+1, 1))

for i in range(shortcutCount):
    start, end, length = map(int, input().split())
    if end > highwayLong: continue
    graph[start].append((end, length))

# 최단거리 리스트를 최대값으로 초기화
distance = [float('inf')] * (highwayLong + 1)
# 시작위치는 0으로 변경
distance[0] = 0

# BFS와 비슷한 로직
queue = []
# 시작 위치의 (cost, node)를 push
heapq.heappush(queue, (0, 0))
while queue:
    # 거리, 정점
    dst, cur = heapq.heappop(queue)
    # 지름길 거리가 더 멀면
    if distance[cur] < dst:
        continue
    # 지름길 거리가 더 가까우면
    for end, length in graph[cur]:
        cost = dst + length
        if distance[end] > cost:
            distance[end] = cost
            heapq.heappush(queue, (cost, end))
# print(distance)
print(distance[highwayLong])

➡ 이해하면서 주석을 달아보았는데 모든 노드를 1로 설정해서 초기화하는건지... 모르겠다... 어렵다...🤪