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에 업데이트 해줬습니다.
'알고리즘 > 백준알고리즘' 카테고리의 다른 글
[백준알고리즘/10816/파이썬] 숫자카드2 (0) | 2022.07.18 |
---|---|
[백준알고리즘/9012번/파이썬] 괄호 (0) | 2022.07.15 |
[백준알고리즘/18352번/파이썬] 특정거리의 도시 찾기 (0) | 2022.07.13 |
[백준알고리즘/1916번/파이썬] 최소비용 구하기 (0) | 2022.07.12 |
[백준알고리즘/1697번/파이썬] 숨바꼭질 (0) | 2022.07.08 |