백준 1446번: 지름길 (S1) - Python 풀이

문제 설명

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

요약) N개의 지름길이 있고, 지름길을 사용 or 안 사용하여 고속도로의 총 길이 D를 최소 거리로 운전하고 싶은 상황입니다. 이 문제의 놀라운 점은 지름길. 이라고 해놓고 지름길을 사용했을 때 더 손해인 경우가 있다는 점입니다. 정신을 잘 차리고 풀어야 합니다.

입력

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

예제 입력 1

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

소신 발언: 고속도로 길이가 150인데 대체 151의 값은 왜 있는 건지 모르겠습니다. 저의 경우, 이런 애들은 싸그리 제외시켰습니다.

출력

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

예제 출력 1

70

 

풀이 과정

거리의 최솟값을 구하기 위해서 다익스트라 알고리즘을 사용할 수 있습니다.

1. 시작 노드에서 나머지 노드까지의 최단 거리를 구하는 경우, 시작 노드와 연결된 노드 중 거리가 가장 작은 노드를 돌아가며 선택합니다.
2. 노드를 도는 중에 더 짧은 거리를 발견하면 최단 거리 값을 갱신합니다.

다익스트라 알고리즘은 DP 유형으로도 볼 수 있는데, 그 이유는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 사용하기 때문입니다.

거리가 가장 작은 노드를 찾을 때 for문을 사용하여 선형적으로 구현하는 방법도 있지만, 이 부분을 힙(우선순위 큐)으로 구현하면 시간복잡도를 낮출 수 있습니다.

import heapq

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

# 고속도로의 길이만큼 2차원 배열 graph 생성
graph = [[] for _ in range(D+1)]

# 무한 값을 10^8으로 초기화
INF = 1e8

# 시작 지점에서 각 노드까지의 거리를 저장할 최단거리 배열
# ex) shortest_distance[3]은 시작 지점에서 3번 노드까지의 최단거리
# INF로 초기화
shortest_distance = [INF] * (D+1)

# 0에서 길이 D까지 가야 하기 때문에
# 1씩 증가하는 노드 D개를 만들어서 graph를 초기화한다
# -> 지름길이 없는 구간에서 사용 가능하도록
for i in range(D):
    graph[i].append((i+1, 1))

# 지름길의 개수만큼 돌면서
for _ in range(N):
    # 입력 받고
    start, end, dist = map(int, input().split())
    # 도착지가 최종 길이를 넘는 경우는 무시
    if end > D: continue
    # 유효한 범위의 입력이면 graph에 저장
    # start 시작 노드에서 end 도착 노드까지 dist만큼 걸린다는 뜻
    graph[start].append((end, dist))

# start 시작 지점에서 다른 노드까지의 최단거리를 구하기 위한
# 다익스트라 알고리즘
def dijkstra(start):
    # 큐 초기화
    q = []
    # start에서 start까지는 거리가 0
    shortest_distance[start] = 0
    # heapq을 통해 q를 최소힙으로 만든다
    # 최소힙에 (거리, 도착 지점) 형태로 값을 push
    # 첫 번째 요소인 거리를 기준으로 최소힙이 구성된다
    heapq.heappush(q, (0, start))

    # q에 값이 존재하면 반복
    while q:
    	# q에서 거리가 가장 작은 값을 pop
        # 시작 지점에서 now까지의 거리가 now_distance라는 뜻
        now_distance, now = heapq.heappop(q)
    
        # now와 연결된 노드들을 순회
        # end: 연결된 노드, dist_to_end: now에서 end까지의 거리
        for end, dist_to_end in graph[now]:
            # 현재 노드 now까지의 거리 now_distance에 dist_to_end를 더한 값 new_dist
            new_dist = now_distance + dist_to_end
            # 시작 지점에서 end까지의 현재 최단거리 값이 new_dist 값보다 크다면
            # 즉, now 노드를 거쳐서 end에 도달하는 new_dist 값이 더 최단이라면
            if shortest_distance[end] > new_dist:
            	# 그 값으로 end까지의 최단거리를 업데이트
                shortest_distance[end] = new_dist
                # 새로운 최단거리와 end를 q에 push
                heapq.heappush(q, (new_dist, end))

# 시작 노드 0에서 다른 노드까지의 최단거리를 구한다
dijkstra(0)

# 최단거리 배열의 인덱스 D의 값을 가져와서
# 0에서 D까지 가는 최단거리를 출력한다
print(shortest_distance[D])

while문 안의 내용이 다익스트라 알고리즘의 핵심입니다.
다시 봤을 때에도 이해하기 쉽도록 주석을 아주 세세하게 적어봤습니다.

사실 이 문제의 경우 방향 그래프이니 그냥 기본 형태의 다익스트라로 구현하면 되는데,

0에서 150(D)까지 가야 한다고 했을 때 모든 길이 지름길로 연결되어 있는 것이 아니기 때문에 즉, 지름길이 없는 구간에서는 일반 경로로 이동(예: 100에서 110까지 지름길이 없기 때문에 110-100=10만큼 이동해야 함) 해야 하기 때문에, D만큼 돌면서 i에서 i+1까지 길이 1로 연결된 노드 D개로 graph를 초기화 하는 생각을 했어야 하는 문제입니다.

 

이상입니다.