백준 2206문제

 

from sys import stdin
from collections import deque

n, m = map(int, stdin.readline().split())
graph = [list(stdin.readline()) for _ in range(n)]
visit = [[[0] * 2 for _ in range(m)] for _ in range(n)]

queue = deque([(0, 0, 0)])
visit[0][0][0] = 1
while queue:
    cnt = 0
    x, y, flag = queue.popleft()  # flag는 벽 파괴 여부 0 : none 1 : done
    if x == n - 1 and y == m - 1:
        break
    for dx, dy in (1, 0), (-1, 0), (0, 1), (0, -1):
        if 0 <= x + dx < n and 0 <= y + dy < m:
            # flag 상관없이 BFS 진행 (방문경험 없고 갈수 있는 길인 경우)
            if visit[x + dx][y + dy][flag] == 0 and graph[x + dx][y + dy] == '0':
                queue.append((x + dx, y + dy, flag))
                visit[x + dx][y + dy][flag] = visit[x][y][flag] + 1
            # 갈수 있는 길이 없는 경우 flag가 0이면 벽 부순다
            elif flag == 0:
                if visit[x + dx][y + dy][1] == 0 and graph[x + dx][y + dy] == '1':
                    queue.append((x + dx, y + dy, 1))
                    visit[x + dx][y + dy][1] = visit[x][y][0] + 1
# [0, 0]이면 -1, [10, 0]이면 10, [n, m]이면  min(n, m) print
ans = min(visit[n - 1][m - 1]) if all(cnt > 0 for cnt in visit[n - 1][m - 1]) else max(visit[n - 1][m - 1])
print(-1 if ans == 0 else ans)

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