[백준] 지름길(python)

백준, 지름길

1446번: 지름길

TL;DR

• 최단 경로 찾기 - 다익스트라 알고리즘(Dijkstra algorithm)

문제 요약

1. D킬로미터의 고속도로에 존재하는 지름길을 이용했을 때 가장 짧은 거리를 출력하는 프로그램을 작성하라.

 

- 0부터 D 킬로미터 떨어진 고속도로에서 지름길들에 대한 정보가 주어질 때 각 길을 사용했을 때 최단 거리로 목적지에 도착할 수 있는 거리를 계산하면 되는 프로그램이다.

입출력 형태

입출력 예시

 

예시 1 :: 이 경우 가장 짧은 경로는 0 ~ 50까지 10인 지름길을 쓰고, 50 ~ 100까지 10인 지름길을 쓰고 100부터 150까지 원래의 고속도로를 타면 70이면 도착할 수 있다.

예시 2 :: 0 ~ 50까지 고속도로를 이용한 후 50 ~ 90까지 20인 지름길 이용, 다시 90 ~ 100까지 고속도로를 이용하면 80이면 도착할 수 있다.

풀이

출발지로부터 목적지까지 주어진 길 중에 최단 경로를 찾는 문제이다.

import sys
from collections import defaultdict
INPUT = sys.stdin.readline

N, D = map(int, INPUT().split())
graph = defaultdict(list)
for _ in range(N):
  a, b, w = map(int, INPUT().split())
  graph[a].append((b, w))

dists = [i for i in range(D + 1)]
for i in range(D + 1):
  if i > 0:
    dists[i] = min(dists[i], dists[i - 1] + 1)
  
  if i in list(graph):
    for v, w in graph[i]:
      if v <= D and dists[v] > dists[i] + w:
        dists[v] = dists[i] + w

print(dists[D])

 

지름길 정보를 graph에 저장한다. 각 도착지까지 걸리는 거리는 해당 도착지까지의 수로 dists 리스트로 표현한다.

시작지점부터 도착지점까지 반복문을 통해 각 지점까지 걸리는 최단 경로를 갱신해간다.

- 우선, 각 지점마다 걸리는 누적 거리를 갱신하기 위해 이전 지점까지의 거리를 더해서 누적 거리를 저장한다.

- 만약 도착한 지점에서 지름길 정보가 존재하고, 갈 수 있는 지름길의 도착지가 최종 목적지와 같거나 작은 경우 지름길을 이용하는 경우와 그냥 고속도로를 이용하는 경우를 비교해서 더 짧은 길로 거리를 갱신해준다. 이 구문을 통해서 짧은 지름길을 사용했을 때로 갱신이 된다.

이 구문이 실행되고 나면 dists는 각 지점까지 운전해야 하는 거리의 최단 경로가 저장된다. 우리가 알고 싶은 값은 입력받은 D까지 이므로 해당 인덱스를 출력하면 정답을 얻을 수 있다.

 

다익스트라 알고리즘이지만, heapq를 사용하지 않고 풀 수 있는 문제이다.