BFS - 미로 탈출

< 미로 탈출 > 

[문제]

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

[입력]

첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

[출력]

첫째 줄에 최소 이동 칸의 개수를 출력한다.

예제 입력	예제 출력
5 6 101010 111111 000001 111111 111111	10
3 3 110 010 011	5

---

아이디어

1. 큐에 시작점을 넣는다.
2. 큐에서 맨 앞 노드를 빼고, 시작점의 조건이 맞는 인접한 노드에 접근한다. 방문처리 하고 큐에 삽입한다.(거리도 큐에 같이 삽입한다.)
3. 반복

풀이 및 코드

from collections import deque
board = []
n, m = map(int, input().split())
for _ in range(n):
    board.append(list(map(int,input())))
queue = deque([])
# row, col, cnt
queue.append((0, 0, 1))
board[0][0] = 0

while queue:
    row, col, cnt = queue.pop()
    # 도착
    if (row == n - 1) and (col == m - 1):
        print(cnt)
        break
    # 네 방향에 접근
    for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        new_row = row + direction[0]
        new_col = col + direction[1]
        # 맵 이탈
        if (not 0 <= new_row <= n - 1) or (not 0<= new_col <= m - 1):
            continue
        # 만약 방문하지 않았으면 방문
        if board[new_row][new_col]:
            board[new_row][new_col] = 0
            queue.append((new_row, new_col, cnt + 1))

나동빈님의 코드를 보자.

나동빈님이 강의에서 보여준 코드이다.

나동빈님은나동빈 님은 그래프에 저장된 값이 1인 경우에만 접근한 것은 나와 비슷하다. 하지만 나는 그래프에 0을 저장하면서 더 이상 접근할 수 없도록 하였다. 반면에 나동빈 님은 그래프에 거리를 저장하면서 나의 cnt변수를 대체하였고, 큐에 저장되는 개수가 적어 나보다 메모리를 덜 사용하는 코드를 구현하였다.