Baekjoon Training #1446

---

#1446 지름길

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9)

#다익스트라 알고리즘 기본 함수 이용
def dijkstra(start):
    queue = []
    distance[start] = 0                 #시작 값은 0으로 설정
    heapq.heappush(queue,(0,start))     #시작 노드부터 탐색

    while queue:    #queue에 남은 노드가 없으면 반복문 종료
        cur_distance, cur_destination = heapq.heappop(queue)    #탐색할 노드와 거리 가져옴
        #현재 거리가 기존의 거리보다 크면 고려하지 않음
        if cur_distance > distance[cur_destination]:
            continue

        for i in graph[cur_destination]:
            cost = cur_distance + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(queue,(cost, i[0]))

sc_num, total_distance = map(int,input().split())
graph = [[] for _ in range(total_distance+1)]
distance = [INF] * (total_distance+1)

#거리 1로 초기화
for i in range(total_distance):
    graph[i].append((i+1, 1))

#지름길 있는 경우에 업데이트
for _ in range(sc_num):
    sc_start, sc_end, sc_length = map(int,input().split())
    #지름길 도착 위치가 총 길이 보다 길면 고려하지 않음
    if sc_end > total_distance:
        continue
    graph[sc_start].append((sc_end,sc_length))

dijkstra(0)
print(distance[total_distance])

이전에 공부했던 dijkstra's algorithm 문제중 실패했던 문제를 다시 풀어보았다.

Dijkstra 문제였기에 기본 함수를 이용하여 풀이를 진행하였다. Dijkstra 기본 함수는 이전에 algorithm글에서 소개하였다.

지름길 수만큼 반복하는 반복문에서는 지름길의 끝점이 총 거리를 넘으면 해당 지름길은 고려하지 않고 그렇지 않은 경우 graph에 추가해준다. 코드 실행은 성공했으나 좀더 깔끔한 풀이가 존재할 것 같아서 구글링을 한결과 더 좋은 코드를 찾았다.

---

import sys

num, distance = map(int, sys.stdin.readline().split())
graph = [list(map(int, input().split())) for _ in range(num)]
dis = [i for i in range(distance+1)]

# 0부터 고속도로의 길이까지 반복하여 확인
for i in range(distance+1):

    # 지름길로 간 거리와 고속도로로 간 거리를 비교하여 더 짧은 거리로 설정
    dis[i] = min(dis[i], dis[i-1]+1)

    # 지름길을 반복하여 최단 거리를 찾는다.
    for start, end, shortcut in graph:
        if i == start and end <= distance and dis[i]+shortcut < dis[end]:
            dis[end] = dis[i]+shortcut

# 고속도로의 끝에 도착했을 때까지 걸린 거리를 출력
print(dis[distance])

이는 보다 직관적이고 단순한 좋은 코드로 보인다. 지름길로 갔을 때와 지름길을 이용하지 않았을 때의 거리를 비교하여 더 짧은 거리를 지속적으로 이용하여 최단거리를 결정한다.

---