백준 2178 미로 탐색

 

from collections import deque

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)

# n -> y   m -> x
n, m = map(int, input().split())

labyrinth = [input() for _ in range(n)] # n개의 배열 m의 길이
check = [[False] * m for _ in range(n)]

deq = deque()
deq.append((0, 0, 1))

check[0][0] = True


def err(a, b):
    return 0 <= a < m and 0 <= b < n


while len(deq) > 0:
    y, x, d = deq.popleft()

    if x == m - 1 and y == n - 1:
        print(d)
        break

    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        dd = d + 1

        if err(xx, yy) and not check[yy][xx] and labyrinth[yy][xx] == '1':
            deq.append((yy, xx, dd))
            check[yy][xx] = True

 

BFS를 이용해 해결했다.

 

큐를 이용해 미리 찍어놓은 좌표대로 움직이도록 했다.

 

마지막 좌표에 도달하면 정답을 출력하도록 했다.