새싹프로그래머의 이야기

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

문제: 고속도로 길이와 지름길이 주어졌을 때, 고속도로를 운전해야하는 최소 거리를 구하는 문제 입니다.

풀이 방법:  다이크스트라 알고리즘을 활용하였습니다. 알고리즘을 활용하여, 지름길 정보에 대해 계속해서 갱신해주는 방식을 사용하였습니다.

풀이 코드:

import sys
import heapq
MAX = 10001

n,d = map(int,sys.stdin.readline().rstrip().split())

road = [[]*(MAX) for _ in range(MAX)]
heap = []
dist = [i for i in range(MAX)]

for _ in range(n):
    start, end, cost = map(int,sys.stdin.readline().rstrip().split())
    heapq.heappush(heap,(end,start,cost))

while heap:
    newEnd, newStart, newCost = heapq.heappop(heap)

    if newCost > (dist[newEnd] - dist[newStart]) or newEnd > d:
        continue

    distance = dist[newStart] + newCost

    if dist[newEnd] > distance:
        dist[newEnd] = distance

    for i in range(newEnd+1,MAX):
        dist[i] = min(dist[i],dist[i-1]+1)

print(dist[d])

풀이 설명:

dist = [i for i in range(MAX)]

먼저 지름길이 없을 경우에는 목적지 x 까지 주행해야 하는 거리는 x이므로, 다음과 같이 저장해줬습니다.

for _ in range(n):
    start, end, cost = map(int,sys.stdin.readline().rstrip().split())
    heapq.heappush(heap,(end,start,cost))

지름길에 대한 정보를 heapq를 활용해 저장하였습니다. 다만 저장할 때, 출발점으로부터 가까운 지름길 정보부터 갱신해주기 위해 (end,start,cost)형태로 저장하였습니다.

*heapq.heappush를 사용하면 end 값 기준으로 오름차순 정렬하여 데이터가 저장됩니다.

while heap:
    newEnd, newStart, newCost = heapq.heappop(heap)

    if newCost > (dist[newEnd] - dist[newStart]) or newEnd > d:
        continue

    distance = dist[newStart] + newCost

    if dist[newEnd] > distance:
        dist[newEnd] = distance

그런 다음 저장된 값을 순차적으로 접근하면서, 지름길에 대한 정보를 업데이트 해줬습니다. 

기존에 다른 지름길을 통해 이미 end값 까지 도착하는 거리가 갱신되었을 수 있으므로, if문을 통해 현재 계산된 거리와 기존에 저장된 거리를 비교하여 최소값을 저장해주었습니다.

for i in range(newEnd+1,MAX):
    dist[i] = min(dist[i],dist[i-1]+1)

마지막으로, 지름길 정보가 갱신 될 때 마다 지름길에 대한 정보를 전체 거리정보가 담겨있는 dist에 업데이트 해줬습니다.