문제: https://www.acmicpc.net/problem/2178

풀이

bfs로 해결한 문제.
항상 도착위치로 이동할 수 있는 경우만 입력으로 주어지기 때문에 이중 반복문을 사용하지 않고 시작점((0, 0))만 큐에 넣어두고 시작했다.
또한 이동하는 다음 좌표의 값 (maze[next_x][next_y])을 바로 이전 좌표의 값(maze[x][y])에 1을 더한 값으로 바꾸게 해 바로 이동 칸 수를 알 수 있도록 했다.
다만 시작점(maze[0][0])이 다시 큐에 들어가는 상황을 막기 위해 movable 함수에 예외를 두게 했다.

소스코드

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

def movable(x, y, n, m, maze):
    if x != 0 or y != 0:
        return 0 <= x < n and 0 <= y < m and maze[x][y] == 1
    return False

def bfs(maze, queue, n, m):
    while queue:
        x, y = queue.popleft()

        DELTAS = ((1, 0), (-1, 0), (0, 1), (0, -1))
        for dx, dy in DELTAS:
            next_x, next_y = x + dx, y + dy
            if movable(next_x, next_y, n, m, maze):
                queue.append((next_x, next_y))
                maze[next_x][next_y] = maze[x][y] + 1


n, m = map(int, input().strip().split())
maze = [[int(x) for x in input().strip()] for _ in range(n)]
queue = deque()
queue.append((0, 0))

bfs(maze, queue, n, m)
print(maze[n-1][m-1])