2178번 미로탐색 [Python]

dfs로 풀어보았따.

def dfs(y, x, depth):
    if x < 0 or y < 0 or y >= N or x >= M: #영역초과
        return

    if y == N-1 and x == M-1: #도착
        global Min
        if depth < Min:
            Min = depth
        return

    for i in range(4):
        wX = x + dir[i][0]
        wY = y + dir[i][1]
        if wX < 0 or wY < 0 or wY >= N or wX >= M:  # 영역초과
            pass
        elif visit[wY][wX] == 0 and map[wY][wX] == '1':
            visit[wY][wX] = 1
            dfs(wY, wX, depth+1)
            visit[wY][wX] = 0


N, M = map(int, input().split())
map = [""] * N
visit = [[0] * M for _ in range(N)]
dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]

Min = N*M

for i in range(N):
    map[i] = input()

dfs(0,0,1)
print(Min)

근데 런타임에러로 안된다;; 재귀를 사용해서그런가. 스택으로 변환해보려다가 이런문제는 bfs로 푸는거라고 인터넷지식인분들이 말씀해주셔서 bfs를 공부해서 풀어보았다.

그래서 bfs로 풀었다

def bfs():
    arr = []
    arr.append([0, 0])
    visit[0][0] = 1
    while arr:
        cur = arr.pop(0)
        x = cur[0]
        y = cur[1]
        if cur == [row-1, col-1]:
            print(visit[x][y])
            break
        now = visit[x][y]
        for i in range(4):
            wx = x + dir[i][0]
            wy = y + dir[i][1]
            if wx >= row or wy >= col or wx < 0 or wy < 0:
                continue
            if visit[wx][wy] == 0 and map[wx][wy] == '1':
                visit[wx][wy] = now + 1
                arr.append([wx, wy])

row, col = map(int, input().split())
map = [""] * row
visit = [[0] * col for _ in range(row)]
dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]

for i in range(row):
    map[i] = input()

bfs()