백준 2178 미로탐색

미로탐색

계획

• BFS. 큐 사용

import sys
from collections import deque

N, M = map(int, input().split())
map_lst = []
count_lst = []
for _ in range(N):
    map_lst.append(list(map(int, input())))
    count_lst.append([0] * M)

# 상 우 하 좌
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def bfs(x, y):
    queue = deque([[x, y]])
    map_lst[y][x] = 0
    while queue:
        index = queue.popleft()
        x = index[0]
        y = index[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= M or ny >= N:
                continue
            if map_lst[ny][nx] != 0:
                map_lst[ny][nx] = 0
                count_lst[ny][nx] = count_lst[y][x] + 1
                queue.append([nx, ny])

bfs(0, 0)
print(count_lst[N-1][M-1]+1)