[백준][Dijkstra/다익스트라] 2206.벽 부수고 이동하기 (파이썬/Python)

<오답>

import sys
import heapq
input = sys.stdin.readline
INF = 1e9

def dijkstra(n,start,end,graph):
    q = []
    dist = [INF]*(n+1)
    dist[start] = 0

    heapq.heappush(q,[start,0])

    while q:
        pos, cost = heapq.heappop(q)
        for p,c in graph[pos]:
            c += cost
            if c < dist[p]:
                dist[p] = c
                heapq.heappush(q,[p,c])
    return dist[end]


n = int(input()) #도시 개수
m = int(input()) #버스 개수
graph = [[] for i in range(n+1)]


for i in range(m):
    a,b,cost = map(int,input().split())
    graph[a].append((b,cost)) 

start, end = map(int,input().split())

print(dijkstra(n,start,end,graph))

# 시간초과

 

 

<정답>

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
INF = 1e9

n = int(input()) #도시
m = int(input()) #버스
graph = [[] for i in range(n + 1)]
dist = [INF] * (n+1)

for i in range(m):
    # a -> b로 가는 비용이 cost라는 것
    a, b, cost = map(int, input().split())
    graph[a].append([b, cost])
start, end = map(int, input().split())

def dijkstra(start):
    dist[start] = 0 #시작점은 0으로 초기화
    heap = []
    heappush(heap, [0, start]) #시작점 넣어주기.
    
    while heap:
        w, n = heappop(heap)
        if dist[n] < w:
            continue
        for n_n, wei in graph[n]:
            n_w = w + wei
            if dist[n_n] > n_w:
                dist[n_n] = n_w
                heappush(heap, [n_w, n_n])
    
dijkstra(start)
print(dist[end])

 

 

---

다익스트라 vs BFS (최단거리 문제에서 언제 어떻게 사용될까?)

 

다익스트라 알고리즘의 경우엔 가중치가 있고 negative edge(음수)가 없을 때 최단거리를 구하기 위해 사용한다. 사용법은 BFS와 매우 유사하고 이때 다익스트라 알고리즘의 경우엔 heap을 사용해 문제를 푼다. 

 

BFS의 경우엔 최단 거리를 구할 때 사용된다는 것이 다익스트라 알고리즘과 같지만 BFS의 경우엔 가중치가 존재하지 않고 정점에서 정점으로 갈 때 최단 거리를 구할 때만 사용이 가능하다. 이때 BFS는 deque를 사용해서 문제를 푼다. 

 

	공통점	차이점
다익스트라	두 알고리즘 모두 최단 거리를 구하는 문제가 주어졌을 때 사용한다.	heap을 사용한다. 가중치가 있고 negative edge가 없을 때 사용한다. (가중치가 다를 때)
BFS(너비 우선 탐색)		deque를 사용한다. 가중치가 없을 때 사용한다.(가중치가 같을 때)