[BOJ] 2206. 벽 부수고 이동하기(python)

📌문제

💪아이디어

1. 이동하기
   가중치 없는 이동의 경우 bfs를 사용하여 상하좌우 이동한다.
   

2. 벽 부순상태인지 체크하기
   가려고하는 위치에 벽의 유무와 그 전에 어떤 상태로 방문했는지에 따라 점수가 달라진다.
   

• 현재 위치에 벽을 부순 적 X 상태로 방문한 적 없는 경우
  
  • 현재 부순 적 X 상태이고, 벽 X 경우
    
    
• 현재 위치에 벽을 부순 적 O 상태로 방문한 적이 없는 경우
  
  • 현재 부순 적 O상태이고, 벽 X 경우
    
  • 현재 부순 적 X 상태이고, 벽 O인 경우
    

🥂코드

import sys; input = sys.stdin.readline
from collections import deque

n, m = map(int,input().split())
board = [list(input().rstrip()) for _ in range(n)]

def bfs():
    dy, dx = (-1,0,1,0), (0,1,0,-1)
    visited = [[[False for _ in range(2)] for _ in range(m)] for _ in range(n)]

    queue = deque()
    queue.append((0,0,1,0))

    visited[0][0][0], visited[0][0][1] = True, True

    while queue:
        y, x, cnt, chk = queue.popleft()
        if y == n-1 and x == m-1:return cnt

        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < n and 0 <= nx < m:
                if not visited[ny][nx][0] and board[ny][nx] == '0' and not chk:
                    visited[ny][nx][0] = True
                    queue.append((ny,nx,cnt+1,chk))
                if not visited[ny][nx][1]:
                    if (board[ny][nx] == '1' and not chk) or (board[ny][nx] == '0' and chk):
                        visited[ny][nx][1] = True
                        queue.append((ny,nx,cnt+1,1))
    return -1

print(bfs())