[BOJ/백준] 17396 백도어 - 파이썬

문제

백준 17396 백도어

 

https://www.acmicpc.net/problem/17396

17396번: 백도어

 

문제풀이

백도어 하는데 걸리는 최단시간을 구하는 문제로 각각의 분기점으로 가는 시간이 가중치가 되는 다익스트라 문제

(n-1)번째 분기점은 값이 1이어도 갈 수 있는 분기점이기에 값이 0인 분기점과 동일

이를 제외한 분기점은 값이 1이라면 continue 해주기

 

개념정리

다익스트라는 최단경로 탐색 알고리즘으로 시작점으로부터 다른 모든 점까지의 최단거리를 구하는데 쓰인다.

bfs도 최단경로 탐색 알고리즘이지만 차이점이 있다면, bfs는 간선의 가중치가 1로 동일한 경우에 적용하고

다익스트라는 가중치가 음이 아닌 값인 경우에 적용한다.

heapq 모듈을 사용하여 구현!

 

코드

import sys
import heapq
inf=sys.maxsize
input=sys.stdin.readline

n,m=map(int,input().split())
can=list(map(int,input().split()))
can[-1]=0 ##넥서스에는 방문 가능
link=[[] for _ in range(n)]
for i in range(m):
     a,b,t=map(int,input().split())
     link[a].append([b,t])
     link[b].append([a,t])

heap=[]
heapq.heappush(heap,[0,0])
dp=[inf for _ in range(n)]
dp[0]=0

while(heap):
    w,now=heapq.heappop(heap)
    if dp[now]<w:
        continue
    else:
        for nxt,nxt_w in link[now]:
            wei=nxt_w+w
            if dp[nxt]>wei and can[nxt]==0:
                dp[nxt]=wei
                heapq.heappush(heap,[wei,nxt])

result=dp[n-1]
print(result if result<inf else -1)

 

 

어려웠던 점

처음에 dp[now]<w인 경우 즉, 갱신 전 값이 이미 더 작은 경우를 continue하지 않고 풀었더니 시간초과가 났다.

다익스트라 알고리즘을 사용할때는 continue문을 적절히 활용해서 시간을 줄이는 것이 중요한 듯!!