미로탐색

문제

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

문제 파악

미로가 주어졌을 때, (1,1)에서 (N,M)까지 이동할 수 있는 최소 칸 수를 구하는 문제
1은 이동 가능, 0은 벽이고 상하좌우로만 이동할 수 있음

접근 방법

•	BFS(너비 우선 탐색) 써야 돼. 왜냐면 최단 거리를 구하는 문제
•	방문한 위치는 재방문하지 않도록 체크
•	현재 위치 기준으로 네 방향으로 움직이며 거리 갱신

문제 풀이

from collections import deque

def solution(maze):
    n, m = len(maze), len(maze[0])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque()
    queue.append((0, 0))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1
                queue.append((nx, ny))

    return maze[n-1][m-1]