[Python] 백준 2178 미로탐색

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

2178번: 미로 탐색

 

문제

 

코드

from collections import deque

n, m = map(int, input().split())
board = [input() for _ in range(n)] # 101111, 101010, 101011, 111011 들어갈 것임
checkArray = [[False] * m for _ in range(n)]

q = deque()
q.append((0, 0, 1))
checkArray[0][0] = True

def isValidCoord(y, x):
    return 0 <= y < n and 0 <= x < m

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

while q:
    y, x, d = q.popleft()
    
    if y == n-1 and x == m-1:
        print(d)
        break

    for i in range(4):
        ny = y + dy[i]  # next y, x
        nx = x + dx[i]
        nd = d + 1
        
        if not isValidCoord(ny, nx): # 범위 내에 있지 않으면 continue
            continue
        if checkArray[ny][nx]: # 이미 방문한 곳이면 continue
            continue
        if board[ny][nx] == '0': # 방문한 곳이 0이라면 continue
            continue
        
        checkArray[ny][nx] = True
        q.append((ny, nx, nd))