괴물 탈출

from collections import deque

n, m = map(int, input().split())
ary = []
for i in range(n):
    ary.append(list(map(int, input())))
    
#상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    q = deque()
    q.append((x, y))
    
    while q:
        x, y = q.popleft()
        
        #상하좌우 방문
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            #범위 벗어나면 continue
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            
            #괴물 만나면 continue
            if ary[nx][ny] == 0:
                continue
            
            #한번도 방문하지 않은 곳이여야 체크한다.
            if ary[nx][ny] == 1:
                ary[nx][ny] = ary[x][y] + 1
                q.append((nx, ny))
    return ary[n-1][m-1]

print(bfs(0,0))

가까운 지점부터 탐색하는 bfs 알고리즘을 사용하면 효율적으로 풀 수 있는 문제이다.

상하좌우를 탐색하도록 한다.

그렇기에 처음 방문하는 곳에 가면 이전 칸도 다시 탐색해서 이전 칸도 카운트가 올라간다.

결국 전부다 탐색을 하게된다. 만약 오른쪽 아래 칸에 도착했을 때 멈추는 조건문을 만든다면 불필요한 연산을 줄일 수 있을 것 같다.