백준(2206) - 벽 부수고 이동하기 Python

백준(5639) - 이진 검색 트리

문제풀이: DFS, BFS 파이썬

최근에 풀었던 DFS, BFS 문제 중에 가장 까다로웠더 문제이다. 문제를 제출하면 계속 11% 쯤에서 중단되고 실패했었는데 그 해결법은 visit 리스트에서 벽을 부수고 진행했는지, 부수지 않고 진행했는지를 나누어서 visit을 처리해야하는 것을 간과했기 때문이다.

해결법은 visit을 3차원 리스트로 두고 풀어야 한다.

from collections import deque
import sys
input = sys.stdin.readline
answer = 0

mx = [0, 0, -1, 1]
my = [1, -1, 0, 0]

n, m = map(int, input().split())
arr = []
for _ in range(n):
    x = input().rstrip()
    arr.append(list(x))

visit = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(2)]
visit[1][0][0] = 1

q = deque()
q.append((0, 0, 1, 1))
while q:
    x, y, distance, wall = q.popleft()
    if x == n-1 and y == m-1:
        answer = distance
        break
    else:
        for i in range(4):
            dx = x + mx[i]
            dy = y + my[i]
            if 0 <= dx < n and 0 <= dy < m:
                if visit[wall][dx][dy] == 0:
                    if arr[dx][dy] == '0':
                        visit[wall][dx][dy] = 1
                        q.append((dx, dy, distance+1, wall))
                    elif arr[dx][dy] == '1' and wall:
                        visit[wall][dx][dy] = 1
                        q.append((dx, dy, distance+1, 0))

if answer == 0:
    print(-1)
else:
    print(answer)