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

https://www.acmicpc.net/problem/2206
실패이유: 구현실패

import collections

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

h, w = map(int, input().split())
board = [list(map(int, list(input()))) for _ in range(h)]
dist = [[[NOT_VISIT] * 2 for _ in range(w)] for _ in range(h)]

queue = collections.deque()
queue.append((0, 0, 0))
dist[0][0][0] = 1

while queue:
    x, y, z = queue.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if board[ny][nx] == 0 and dist[ny][nx][z] == NOT_VISIT:                     # 빈 칸으로 이동하는 경우
                dist[ny][nx][z] = dist[y][x][z] + 1
                queue.append((nx, ny, z))
            if z == 0 and board[ny][nx] == 1 and dist[ny][nx][1] == NOT_VISIT:          # 한번도 벽을 부수지 않았고, 벽으로 이동하는 경우
                dist[ny][nx][1] = dist[y][x][0] + 1
                queue.append((nx, ny, 1))

print(min(dist[-1][-1]) if min(dist[-1][-1]) != NOT_VISIT else -1)

• 정점을 잘 결정해야 한다.
  • 블록을 한번도 부수지 않은 정점과
  • 블록을 한번 부순 정점으로 나눈다.
• dist[y좌표][x좌표][블록 부수기 여부]
  • z = 0 : 블록 안 부숨
  • z = 1 : 블록 부숨
• 정점을 나눴으니, 이동시에도 빈 칸으로 이동하는 경우와 벽으로 이동하는 경우를 나눠서 BFS 처리

출처: 코드플러스 - 알고리즘 중급 1/3 강의
https://code.plus/course/43