이 문제는 2D 배열로 주어진 미로에서, (1, 1)에서 출발해 (N, M)까지 가는 최소 칸 수를 구하는 문제임. 미로에서는 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 의미함. 문제를 풀 때 BFS(너비 우선 탐색) 알고리즘을 사용하면 된다. 이 문제에서는 BFS 알고리즘을 사용해야 하는 이유는, BFS는 가장 짧은 경로를 구할 때 효과적임. BFS는 큐를 사용해서 각 칸을 차례로 방문하며, 최단 경로를 계산하는 방법이다. 나의 풀이 - BFS를 이용해 (1, 1)에서 출발해서 (N, M)까지 최단 거리를 계산. - 큐에 현재 위치를 넣고, 인접한 칸을 차례로 방문. - 이미 방문한 칸은 다시 방문하지 않도록 처리.

from collections import deque

def bfs(maze, N, M):
    # 상, 하, 좌, 우
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # 큐 초기화, (0, 0)에서 시작
    queue = deque([(0, 0)])
    
    # (0, 0)에서부터 각 칸까지의 최소 거리를 기록
    maze[0][0] = 1
    
    while queue:
        x, y = queue.popleft()
        
        # (N-1, M-1) 도달 시 최소 칸 수 리턴
        if x == N - 1 and y == M - 1:
            return maze[x][y]
        
        # 4방향으로 이동
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < N and 0 <= ny < M and maze[nx][ny] == 1:
                queue.append((nx, ny))
                maze[nx][ny] = maze[x][y] + 1

    return -1  # 도달할 수 없으면 -1 (문제에서는 항상 도달 가능하다고 했으므로 이 코드는 사실 필요 없음)

def main():
    N, M = map(int, input().split())
    maze = [list(map(int, input().strip())) for _ in range(N)]
    
    print(bfs(maze, N, M))

if __name__ == "__main__":
    main()

설명 1. bfs 함수: - 큐를 이용하여 (0, 0)부터 시작해 모든 칸을 탐색. - 각 칸에 대해 상하좌우로 인접한 칸을 확인하고, 이동할 수 있으면 큐에 추가. - 각 칸에 도달할 때마다 지나온 칸 수를 기록해 놓고, 목적지인 (N-1, M-1)에 도달하면 그때까지의 칸 수를 반환. 2. main 함수: - 첫 번째 줄에서 N, M을 입력받고, 미로 배열을 받아와서 bfs 함수에 전달. - BFS에서 큐에 들어간 칸은 이미 방문한 칸으로 처리되므로, 추가적으로 방문 여부를 체크할 필요는 없음.