파이썬 알고리즘 308번 | [백준 1446번] 지름길 - 다익스트라 (heapq)

308. 지름길

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

from collections import defaultdict
import sys
import heapq

# N : 고속도로의 개수, D : 고속도로 총길이 
N,D = map(int,sys.stdin.readline().rstrip().split())
graph = defaultdict(list)
shortest = [int(1e9) for _ in range(10000)] # 고속도로 각 구간마다의 최단거리 

# 추가적인 초기화 작업
# 내 현재노드 -> 다음노드 (현재노드+1) 까지의 거리는 1 
for i in range(10000) : 
    graph[i].append((1, i+1))

# 다익스트라 알고리즘 
for i in range(N) : 
    # 지름길의 시작 위치, 도착 위치, 지름길의 길이
    start, end, cost = map(int,sys.stdin.readline().rstrip().split())
    if cost > D : # 지름길이 총 고속도로보다 길어버린 경우 
        continue
    graph[start].append((cost, end)) # start 에서 갈 수 있는 경로들을 저장 
    # 우선순위 큐이기에 금액, 도착지 순으로 넣음 

# 0부터 출발
hq = []
# 0번에서 시작하고, 이때 비용은 0이다.
heapq.heappush(hq, (0,0)) 
while hq : # cost가 작은 아이부터 꺼내야 함
    now_cost, now_node = heapq.heappop(hq)  
        
    if shortest[now_node] < now_cost : # 이 경우엔 비교 조차 안해두 됨 ! 
        continue 
    if(now_node in graph.keys()) : 
        for next_cost, next_node in graph[now_node] :
            if next_node < 10000:  
                if shortest[next_node] > now_cost + next_cost : 
                    shortest[next_node] = now_cost + next_cost 
                    heapq.heappush(hq, (now_cost + next_cost, next_node))

print(shortest[D])

<내 틀렸던 풀이, 문제점>

1. 인덱스 에러 발생

• 문제 조건에서 노드가 10000개 미만이라 했기에, 10000노드에 대한 정보로 shortes와 graph 를 구성해주었다.
• 또한 연속적인 직선길이라서 default 로 처음에 graph 에
  현재 노드가 i이라면 다음 노드로는 무조건 갈 수 있으니, 다음노드 = i+1 비용은 1로 초기화 입력을 시켜줍니다.

from collections import defaultdict
import sys
import heapq

# N : 고속도로의 개수, D : 고속도로 총길이 
N,D = map(int,sys.stdin.readline().rstrip().split())
graph = defaultdict(list)
shortest = [int(1e9) for _ in range(D+4)] # 고속도로 각 구간마다의 최단거리 

# 추가적인 초기화 작업
# 내 현재노드 -> 다음노드 (현재노드+1) 까지의 거리는 1 
for i in range(D+1) : 
    graph[i].append((1, i+1))

# 다익스트라 알고리즘 
for i in range(N) : 
    # 지름길의 시작 위치, 도착 위치, 지름길의 길이
    start, end, cost = map(int,sys.stdin.readline().rstrip().split())
    if cost > D : # 지름길이 총 고속도로보다 길어버린 경우 
        continue
    graph[start].append((cost, end)) # start 에서 갈 수 있는 경로들을 저장 
    # 우선순위 큐이기에 금액, 도착지 순으로 넣음 

# 0부터 출발
hq = []
# 0번에서 시작하고, 이때 비용은 0이다.
heapq.heappush(hq, (0,0)) 
while hq : # cost가 작은 아이부터 꺼내야 함
    now_cost, now_node = heapq.heappop(hq)  

    if shortest[now_node] < now_cost : # 이 경우엔 비교 조차 안해두 됨 ! 
        continue 
    if(now_node in graph.keys()) : 
        for next_cost, next_node in graph[now_node] :  
            if shortest[next_node] > now_cost + next_cost : 
                shortest[next_node] = now_cost + next_cost 
                heapq.heappush(hq, (now_cost + next_cost, next_node))

print(shortest[D]) 

<반성 점>

• 또한 연속적인 직선길이라서 default 로 처음에 graph 에
  현재 노드가 i이라면 다음 노드로는 무조건 갈 수 있으니, 다음노드 = i+1 비용은 1로 초기화 입력을 시켜줍니다.

<배운 점>