[BOJ] 1446번 - 지름길

1446번: 지름길

1446번: 지름길

 

문제 정의

---

모든 지름길은 일방통행이고 고속도로 역주행 금지이다. (고속도로 길이를 넘어서 다시 뒤로 갈 수 없음.) 지름길의 정보가 주어졌을 때, 세준이가 운전해야 하는 거리(길이)의 최솟값을 구하면 된다.

N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다.

 

 

접근 방법

---

처음에 지름길을 많이 사용할 수록 좋다고 판단하여 지름길 정보를 순회하며 거리의 합을 비교하고 최소 거리를 출력하고자했다.

그래서 구현이라 생각하고 조건을 따지며 코딩했지만 시간도 오래걸리고 까다로워서 모범답안을 살펴봤다.

최단 거리를 구하는 것으로 다익스트라 알고리즘으로 접근하면 된다.

다익스트라 알고리즘은 노드와 간선이 있을 때 $O(ElogV)$ 시간 복잡도를 가져 효율적이다.

이 문제에서는 어떤 변수를 노드로 놓을지가 포인트이다.

당연히 간선은 도로의 길이이고 노드의 개수는 N이 아니라, V가 된다.

 

 

문제 해설

---

• 0~D 까지를 각 노드라고 보고 그래프를 생성한다.
• 그래프의 i~i+1 까지의 간선은 1로 설정한다. (길이가 1차이기 때문)
• 다익스트라 알고리즘에 필요한 distance 변수를 D+1 만큼 생성하고, 최단 경로를 업데이트 할 때마다 이 변수에 저장한다.
• 입력받은 N개의 지름길 정보도 그래프 정보에 업데이트 한다.
• 우선순위 큐를 사용해서 다익스트라를 구현한다.
• 0~D 까지의 최단경로 정보가 완성되면, D까지 운전해야 하는 최솟값(최단거리)를 구할 수 있다.

 

 

풀이

---

# 모든 지름길은 일방통행, 고속도로 역주행 금지 (고속도로 길이 넘어서 다시 뒤로 갈 수 없음.)
# 지름길의 정보가 주어졌을 때, 세준이가 운전해야 하는 거리(길이)의 최솟값
# 최단 경로 구하기: 다익스트라 알고리즘

# 노드:1~D 까지

import sys
import heapq
input = sys.stdin.readline

N, D = map(int, input().split())    # 지름길 개수, 고속도로 길이

# 지름길 정보를 담는 리스트
short_path = [[] for i in range(D+1)]   # 2차원 리스트

for i in range(D):
    short_path[i].append((i+1, 1))  # i~i+1의 거리차이가 1임을 저장.
    
for _ in range(N):
    start, end, dist = map(int, input().split())
    if end > D: continue    # 지름길의 도착지점이 목표지점보다 멀다면, 가도 소용없으니 패스
    short_path[start].append((end, dist))

INF = 1e9
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 short_path[now]:
        cost = d + x[1]
        
        if distance[x[0]] > cost:
            distance[x[0]] = cost
            heapq.heappush(q, (cost, x[0]))
            
print(distance[D])

 

 

정리

---

• 시간복잡도는 $O(ElogV)$ 이다.
• 다익스트라 알고리즘은 꼭 알고리즘 틀을 외워놓는게 문제 풀이에 수월할 것 같다.