[백준] 1261번:알고스팟 (python 파이썬)

문제

www.acmicpc.net/problem/1261

1261번: 알고스팟

 

 

풀이 및 소스코드

방문하지 않았고, 벽이 아니라면 덱 앞쪽에 두고,

벽이라면 덱 뒤쪽에 추가하여 bfs를 돌려준다.

import sys
from collections import deque
input = sys.stdin.readline

m, n = map(int, input().split())
miro = [list(map(int,input().rstrip())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

dist = [[-1]*m for _ in range(n)]
q = deque()
q.append((0,0))
dist[0][0] = 0

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