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

https://www.acmicpc.net/problem/2206

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

n, m = map(int,input().split()) # 세로, 가로
board = [list(map(int,input().strip())) for _ in range(n)]

'''
최단경로(시작, 끝 포함)
한개는 부숴도 됨
0 이동가능
1 이동불가

도착못하면 -1 출력
'''

visited = [[[0]*2 for _ in range(m)] for _ in range(n)]
def bfs(si,sj, crash):
    q = deque([(si,sj,crash)]) # 0 이면 벽 안부숨, 1 이면 벽부숨
    visited[sj][si][crash] = 1
    while q:
        i, j, crash = q.popleft()

        if i == m-1 and j == n-1:
            return visited[j][i][crash]

        for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]:
            ni, nj = i+di, j+dj
            if 0<=ni<m and 0<=nj<n:
                # 벽이 아닌 경우
                if board[nj][ni] == 0 and not visited[nj][ni][crash]:
                    visited[nj][ni][crash] = visited[j][i][crash] + 1
                    q.append((ni,nj, crash))
                # 벽인데, 부술 기회가 남아있는 경우
                elif board[nj][ni] == 1 and crash == 0:
                    visited[nj][ni][1] = visited[j][i][crash] + 1
                    q.append((ni,nj, 1))
    return -1

print(bfs(0,0, 0))

내 첫 풀이의 잘못된 점

1. 처음 입력받을 때 너무 당연하게 split()을 했다...

2. 벽 부수는 여부에 따라 visited을 3차원 배열로 만들 생각을 못했다...

3. 최단경로 구할 때 처음과 끝도 포함이므로 visited을 그대로 이용할 거면 +2를 할 필요없이 그대로 출력하면 된다.