[Coding Test][Python][백준] BOJ #1446 지름길

 

 

#1446 지름길

문제)

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D 킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다.

어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력)

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다.

다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력)

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

---

풀이)

※ 풀이 아이디어

최단거리를 구하는 알고리즘입니다. 도로 간 거리가 양수이므로 전형적인 Dijkstra 알고리즘 문제입니다.
하지만, Graph로 주어진 것이 아니라 임의적으로 Graph를 만들어 주어야합니다.
도로 위의 위치를 Node로 생각하고 이를 Graph로 만들어 주면 됩니다.
(지름길의 시작위치, 도착위치, 길이)가 주어지기 때문에 이를 처리하는 것은 쉽지만 일반 도로를 구성하는 것을 생각하는게 조금 까다롭습니다.
이는 i번째 위치 -> i+1 위치로 이동할 때 거리는 1을 가지는 Node와 Edge를 선언해주면 해결 가능합니다.

 

아래 글은 다익스트라 알고리즘에 대한 글입니다.

[Coding Test][Python][Shortest Path] Dijkstra Algorithm(다익스트라) 개념 및 예제

 

from collections import defaultdict
import heapq

N, D = map(int, input().split())
INF = float('inf')
distances = [INF] * (D+1)

roads = defaultdict(list)

# 일반 도로 연결 (i -> i+1의 dist는 1)
# 고속도로를 그냥 직진하는 경우를 고려해야 하기 때문
# 만약 지름길이 연결되지 않는 구간이 있다면, i → i+1을 통해 일반 도로를 타고 가야 함
# 그렇지 않으면 일부 구간에서 이동 불가능한 문제가 발생

# 일반 도로 (i -> i+1, dist = 1)
for i in range(D):
    roads[i].append((i + 1, 1))

# 지름길 정보
for _ in range(N):
    u, v, shortcut_dist = map(int, input().split())
    if v <= D:  # 도착 지점이 D를 넘어가면 무시
        roads[u].append((v, shortcut_dist))
        
def dijkstra(start):
    pq = [(0, start)]  # (거리, 위치)
    heapq.heapify(pq)

    distances[start] = 0  # 시작점 거리 0

    while pq:
        curr_dist, curr_pos = heapq.heappop(pq)

        # 이미 더 짧은 경로가 있을때
        if curr_dist > distances[curr_pos]:  
            continue

        # 현재 위치에서 이동 가능한 경로 탐색
        for next_pos, next_dist in roads[curr_pos]:
            total_dist = curr_dist + next_dist
            if total_dist < distances[next_pos]:
                distances[next_pos] = total_dist
                heapq.heappush(pq, (total_dist, next_pos))

# 다익스트라 실행
dijkstra(0)

# 최단 거리 출력
print(distances[D])