미로만들기 - BOJ

미로만들기 - BOJ

from collections import deque

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

n = int(input())
a = [list(input()) for _ in range(n)]
visit = [[-1] * n for _ in range(n)]
start = (0, 0)

q = deque()
q.append(start)

visit[0][0] = 0

while q:
    x, y= q.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= n:
            continue
        if visit[nx][ny] != -1 :
            continue
        if a[nx][ny] == '0':
            visit[nx][ny] = visit[x][y] + 1
            q.append((nx, ny))
        else:
            visit[nx][ny] = visit[x][y]
            q.appendleft((nx, ny))

print(visit[n-1][n-1])