백준 2206 벽 부수고 이동하기 (파이썬)

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

2206번: 벽 부수고 이동하기

벽을 하나씩 부수고 매 경우마다 bfs를 수행하면 시간 초과가 뜬다

 

1. 맵을 3차원 리스트로 만들어 세번째 차수에는 벽을 뚫었는지 여부를 저장한다

2. 벽이 아닌 경우 일반적인 bfs를 수행한다

3. 벽이고 그 벽을 뚫은 적이 없는 경우 세번째 차수 값을 수정하여 큐에 넣어준다

4. 결과적으로 한 번의 bfs 수행으로 벽을 한 개까지 부쉈을 때 최단 거리를 구할 수 있다

from collections import deque

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

def bfs():
    q.append([0, 0, 0])
    c[0][0][0] = 1
    while q:
        x, y, z = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if a[nx][ny] == 0 and c[nx][ny][z] == -1:
                    c[nx][ny][z] = c[x][y][z] + 1
                    q.append([nx, ny, z])
                elif z == 0 and a[nx][ny] == 1 and c[nx][ny][z+1] == -1:
                    c[nx][ny][z+1] = c[x][y][z] + 1
                    q.append([nx, ny, z+1])

n, m = map(int, input().split())
a = [list(map(int, input())) for _ in range(n)]
c = [[[-1]*2 for _ in range(m)] for _ in range(n)]
q = deque()

bfs()
ans1, ans2 = c[n-1][m-1][0], c[n-1][m-1][1]
if ans1 == -1 and ans2 != -1:
    print(ans2)
elif ans1 != -1 and ans2 == -1:
    print(ans1)
else:
    print(min(ans1, ans2))