[BOJ] 1261번: 알고스팟 (Dijkstra)

 

 

문제 링크

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

 

 

 

TIL

• 조건에 따라 업데이트되는 dist가 다를 수도 있음
  • 이럴 경우 분기해서 처리해야 함
• 항상 heappush 하기 전에 해당 dijk 먼저 업데이트하기 !!

 

 

 

Code

import heapq
import sys
input = sys.stdin.readline

M, N = map(int, input().split())
graph = [list(map(int, list(input().strip()))) for _ in range(N)]

dir = [(0,1), (1,0), (0,-1), (-1,0)]
dijk = [[int(1e9)]*M for _ in range(N)]
dijk[0][0] = 0
q = [(dijk[0][0], 0, 0)] # cnt, y, x

while q:
    cnt, cy, cx = heapq.heappop(q)
    if cnt > dijk[cy][cx]:
        continue

    for dy, dx in dir:
        ny, nx = cy+dy, cx+dx
        if 0<=ny<N and 0<=nx<M:
            if graph[ny][nx] == 1:
                new_cnt = cnt+1
            else:
                new_cnt = cnt

            if new_cnt < dijk[ny][nx]:
                dijk[ny][nx] = new_cnt
                heapq.heappush(q, (new_cnt, ny, nx))

print(dijk[N-1][M-1])