[python] 백준 1261 알고스팟

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

1261번: 알고스팟

 

문제해결

• 다익스트라 (bfs를 이용해 꼭지점간의 최소 거리 측정)
• 벽이 없는 곳은 벽을 깨지 않으므로 비용(cost)가 이전이랑 같다. 따라서 deque()의 왼쪽에 다시 넣는다.
• 벽을 부시면 비용(cost)를 추가 지불 해야하므로 deque()오른쪽에 넣는다.
• deque가 없어질 때 까지 반복한 후 m,n 까지 가는데 비용을 출력한다.

CODE

import sys
from collections import deque
m, n = map(int, input().split())
board = [list(map(int, input())) for _ in range(n)]
move = [(-1,0), (1,0), (0,1), (0,-1)]
dist =[[-1 for _ in range(m)] for _ in range(n)]

q = deque()
q.append((0,0))
dist[0][0] = 0
while q:
    x, y = q.popleft()
    for k in range(4):
        nx = x + move[k][0]
        ny = y + move[k][1]
        if 0 <= nx <n and 0<=ny<m:
            if dist[nx][ny] == -1:
                if board[nx][ny] ==0:
                    dist[nx][ny] = dist[x][y]
                    q.appendleft((nx,ny))
                else:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx,ny))
print(dist[n-1][m-1])