[백준] 2206번 벽 부수고 이동하기

백준 2206 벽 부수고 이동하기

파이썬 기준 재귀의 횟수가 1000번을 넘어가면 Recursion Error가 발생한다. recursion limit을 늘리면 해결할 수 있지만, n과 m의 단위를 보고 DFS보단 BFS를 활용하는 것이 더 적절하겠다고 생각했다. 처음엔 방문했는지 저장하는 toVisit 리스트에 방문했는지 저장했지만, 같은 위치이더라도 벽돌을 깬 적이 있는지 없는지에 따라 다르게 다뤄야 한다는 것을 까먹었다. 즉, toVisit 리스트에는 y와 x좌표뿐만 아니라 벽을 깬 적이 있는지로 나눠서 저장해야 한다. 그러므로 toVisit 리스트는 3차원 리스트가 된다.

평범한 BFS탐색이지만, 벽을 깬 적이 있는지 없는지로 구분해야 하기 때문에, 3차원 리스트로 위치와 벽을 깬 적이 있는지 없는지 저장한다.

import sys
from collections import deque

input = sys.stdin.readline

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

def BFS():
    dq = deque()
    dq.append([0, 0, 0, 1])
    while dq:
        y, x, bc, cnt = dq.popleft()
        if y == n - 1 and x == m -1:
            return cnt
        for d in range(4):
            tmpY = y + dy[d]
            tmpX = x + dx[d]
            if n > tmpY >= 0 and m > tmpX >= 0:
                if toVisit[tmpY][tmpX][bc]:
                    toVisit[tmpY][tmpX][bc] = False
                    if isWall[tmpY][tmpX] and bc == 0:
                        dq.append([tmpY, tmpX, bc + 1, cnt + 1])
                    elif not isWall[tmpY][tmpX]:
                        dq.append([tmpY, tmpX, bc, cnt + 1])
    return -1

n, m = map(int, input().split())
toVisit = [[[True, True] for _ in range(m)] for __ in range(n)]
isWall = []
toVisit[0][0] = [False, False]
for _ in range(n):
    isWall.append(list(map(lambda x: True if x == "1" else False, [s for s in input().strip()])))
print(BFS())