백준 1446. 지름길(다익스트라)

문제 😵‍💫

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D 킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다. 세준이가 운전해야 하는 거리의 최솟값을 출력하시오

 

내 풀🦷

# 1446. 지름길
import sys
import heapq
input = sys.stdin.readline
INF = 1e9

n, d = map(int, input().split())
graph = [[] for _ in range(d + 1)]
distance = [INF] * (d + 1)

for i in range(d):
    graph[i].append((i + 1, 1))

# 지름길 있는 경우 인접 리스트에 추가해주기
for _ in range(n):
    s, e, l = map(int, input().split())
    # 마지막 도착지점이 실제 고속도로 보다 멀면 넘긴다
    if e > d:
        continue
    graph[s].append((e, l))

# print(graph)
distance[0] = 0
heap = [[0, 0]]
while heap:
    dist, now = heapq.heappop(heap)

    if dist > distance[now]:
        continue

    for i in graph[now]:
        mn_dist = dist + i[1]
        if mn_dist < distance[i[0]]:
            distance[i[0]] = mn_dist
            heapq.heappush(heap, (mn_dist, i[0]))

print(distance[d])

 

역주행이 안되는데 들어오기는 실제 고속도로보다 먼곳도 들어오고해서 어떻게 처리해줘야 할지 고민을 오래했다... 그리고 지름길이 있지만 더 멀어서 이용을 안 하는 경우는 어떻게 처리해야할까 고민을 했다...

 

가장 먼저 모든 두 길이1만큼 갈때 1이 걸린다고 초기화해줬고... 지름길 값을 입력하면서 역주행은 할 수 없으므로 마지막 값이 고속도로의 끝을 넘어버리는 경우는 넣어주지 않았다... 

그리고 나머지는 우리가 아는 다익스트라를 사용해서 구현하면 끝!!! 😊😊😊

 

참고하면 좋을 개념들 ✍️

Dijkstra

 

1. 작동원리

• 간선 : 인접 리스트, 거리 배열 : 초기값 무한대로 설정, 힙 시작점 추가
• 힙에서 현재 노드 빼면서, 간선 통할 때 더 거리가 짧아진다면 거리 갱신 및 힙에 추가해준다
• 힙 : 최댓값, 최솟값을 빠르게 찾을 수 있는 자료 구조

 

2. 기본 코드

# 더익스트라 구현하기

# k : 시작점
# dist : 거리배열

dist[k] = 0 
heapq.heappush(heap, (0, K))

while heap:
	w, y = heapq.heappop(heap)
    if w > dist[v] : continue
    for nw, nv in edge[v]:
    	if dist[nv] > dist[v] + nw:
        	dist[nv] = dist[v] + nw
            heapq.heappush(heap, dist[nv], nv))

 

3,  아이디어

• 한점에서 다른 모든 점으로의 최단 경로 > 다익스트라 사용
• 모든 점 거리 초기값 무한대로 설정
• 시작점 거리 0 설정 및 힙에 추가
• 힙에서 하나씩 빼면서 수행할 것
• 현재 거리가 새로운 간선을 거칠때보다 크다면 갱신
• 새로운 거리힙에 추가!!!