1446

날짜 : 2023. 07. 10

사용 언어 : python

 

문제

 

 

코드

import sys
import heapq

def dijkstra(node):  # 시작노드
    q = list()
    heapq.heappush(q, (0, node))
    distance[node] = 0
    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]: continue  # 거리 갱신 필요 없는 경우
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:  # 거리 갱신 가능한 경우
                distance[i[0]] = cost  # 최신화
                heapq.heappush(q, (cost, i[0]))  # heap에 삽입
    return


N, D = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(D + 1)]
for i in range(D):
    graph[i].append((i+1, 1))  # 초기 거리 1로 초기화

distance = [int(1e9)] * (D + 1)

for i in range(N):
    s, e, c = map(int, sys.stdin.readline().split())
    if (e - s) < c or e > D: continue
    graph[s].append((e, c))  # s -> e까지의 거리가 c

dijkstra(0)
print(distance[D])

 

 

풀이

- 다익스트라를 활용하여 풀이한다.

- 0에서 출발하여 D에 도착하는 것이기 때문에 거리를 1마다 존재하는 노드로 산정하여 그래프를 만들어 풀이한다.

(노드 3의 경우에는 2, 4와 연결되어 있지만 방향성이 무조건 증가하기 때문에 4와 연결되어 있고, 그 거리는 1이다. 그래서 (4, 1)인 튜플만 갖게 된다.)

- 그 다음 지름길을 입력받고, 지름길의 도착점이 D보다 큰 경우, 지름길보다 정순으로 이동하는 것이 더 효율적인 경우를 필터링 한 다음 지름길을 적용한다.

- 그 다음 다익스트라를 사용해 시작점부터 각 노드까지의 최소 거리를 구한 후, D까지의 최소거리를 출력한다.

 

 

알게된 점

- 다익스트라를 작년 10월쯤 하고 거의 안풀었다보니 좀 어색하게 느껴졌다.

- 나동빈님의 블로그도 참고하고, 이 풀이방식도 참고하면서 차근차근 풀어보니까 새록새록 생각나는 것 같다.

 

 

참고 사이트

- 다익스트라 : https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

- 풀이 : https://jie0025.tistory.com/200

[BOJ - 다익스트라] 1446번 : 지름길 (python)