[Python] 백준 <1261-알고스팟>

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

 

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

def bfs(a, b):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    dq = deque()
    # 첫 좌표
    dq.append([a, b])
    # 방문 처리
    wall[a][b] = 0

    while dq:
        x, y = dq.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= M:
                continue
            # 미방문시
            if wall[nx][ny] == -1:
                # 빈 방이면 우선 방문하도록 큐의 왼쪽 추가
                if miro[nx][ny] == 0:
                    wall[nx][ny] = wall[x][y]
                    dq.appendleft([nx, ny])
                # 벽이면 부수고 wall 늘리고 오른쪽 추가
                else:
                    wall[nx][ny] = wall[x][y]+1
                    dq.append([nx, ny]) 



M, N = map(int, input().split(" "))
miro = list()
# 0이 빈방, 1이 벽
# (0,0), (N-1,M-1) 항상 빈방
for _ in range(N):
    miro.append(list(map(int, input().strip())))

# 방문 + 벽을 깬 횟수 저장
wall = [[-1]*M for _ in range(N)]

# 최대한 빈방을 먼저 방문하도록 bfs 처리
bfs(0, 0)

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