[BOJ|PYTHON]백준 20046 - 다익스트라

지금껏 다익스트라는 adj라는 배열만 만들어서 사용했었는데, 이 문제는 dijkstra를 눈치채고 다익스트라를 구현하기까지 쉽지 않았다.

일단 맨 처음 문제를 보았을 때에는 floodfill 먼저 떠올랐는데(GridWorld라서 더 그랬다), floodfill과는 결이 다르다. 왜냐면 이미 갔던 곳도 더 빠른 방법이 있다면 왼/오/위/아래 의 방법을 선택해서 빠른 방법으로 갱신해낼 수 있기 때문이다.

그래서 가중치를 가지는 다익스트라로 구현할 수 있다. 다익스트라의 특징은 다음과 같다.

1. 가중치가 모두 양수이다.
2. 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다.
3. 각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 더 작은 값으로 다시 갱신되지 않는다.

우선순위큐를 이용해서 구현할 수 있다.

 

import sys
input=sys.stdin.readline
import heapq
M,N=map(int,input().split())
List=[list(map(int,input().split()))for _ in range(M)]
List_=[[float('inf') for _ in range(N)] for _ in range(M)]
q=[]
heapq.heapify(q)
dx,dy=[-1,1,0,0],[0,0,-1,1]
heapq.heappush(q,[List[0][0],0,0])
List_[0][0]=List[0][0]
while q:
    val,x,y=heapq.heappop(q)
    if List[x][y]==-1: continue
    if List_[x][y]!=val: continue #이 코드줄이 핵심이다. 한 번 우선순위큐로 걸러진 애는 더이상 보지 않는다.
    for i in range(4):
        nx=x+dx[i]; ny=y+dy[i]
        if 0<=nx<M and 0<=ny<N and List[nx][ny]!=-1:
            if List_[nx][ny]>List_[x][y]+List[nx][ny]:
                List_[nx][ny]=List_[x][y]+List[nx][ny]
                heapq.heappush(q,[List_[nx][ny],nx,ny])

if List_[M-1][N-1]==float('inf'): print(-1)
else:
    print(List_[M-1][N-1])