📕문제

[Baekjoon] 1446. 지름길

문제 설명

D킬로미터의 도로에 N개의 지름길이 존재한다고 했을 때, 출발지에서부터 목적지까지 운전하는 최소 거리를 구하는 문제다.
지름길은 시작 지점, 끝 지점, 지름길의 길이 형태로 주어지며, 모든 지름길의 시작 지점은 끝 지점보다 앞에 위치한다(역주행 X).

---

📝풀이

처음 시도했던 방법은 각 지름길의 시작 지점과 끝 지점, 도로의 시작 지점과 끝 지점을 노드로 설정하고 각 지점간의 거리를 비용으로 한 가중치 그래프를 생성하고 다익스트라를 적용하는 방법이었다.

하지만 코드를 작성하다 보니 알고리즘을 적용시키기 위해 데이터를 설정하는 과정이 복잡하다고 느꼈다.(배보다 배꼽이 더 크다는 느낌..)

대충 정리해보자면

• 입력값을 통해 각 노드 간(지름길의 시작점, 끝점) 비용 (지름길의 거리) 저장
• 지름길에 존재하지 않았다면 도로의 시작점과 끝 점 노드 추가
• 위치 기준 오름차순으로 정렬 후 각 노드 간 비용(거리) 저장
• 각 노드 별 최단거리 저장

위 과정을 거치면 공간복잡도 면에서 이득을 보겠지만 그만큼 시간복잡도 면에선 손해를 본다.
따라서 모든 구간을 노드로 설정하기로 했다.

import sys
read = sys.stdin.readline
import heapq

N, D = map(int, read().split())

graph = [[] for _ in range(D + 1)]
distance = [sys.maxsize] * (D + 1)

for i in range(D):
    graph[i].append((i + 1, 1))

for _ in range(N):
    start, end, length = map(int, read().split())
    if end <= D and length < end - start:
        graph[start].append((end, length))

heap = []
heapq.heappush(heap, (0, 0))
distance[0] = 0

while heap:
    n1, d1 = heapq.heappop(heap)

    for n2, d2 in graph[d1]:
        cost = distance[d1] + d2
        if cost < distance[n2]:
            distance[n2] = cost
            heapq.heappush(heap, (cost, n2))

print(distance[D])

• 거리가 자연수로 주어지기 때문에 시작점부터 간격이 1인 모든 구간을 노드로 설정한다.
  시작점부터 각 노드까지의 최단 거리를 저장하기 위한 배열도 만든다.
• 모든 노드에 대해 다음 노드까지의 거리가 1이라는 정보(다음 노드, 1)를 추가한다.
• 주어진 지름길의 정보를 저장한다.
• 우선순위 큐를 이용한다.
  • 초기에 (0, 0)을 추가해 탐색을 시작한다.
  • 해당 노드를 경유한 비용이 더 적으면 값을 업데이트하고 큐에 추가한다.