[python] 백준 2206번 : 벽 부수고 이동하기 (3차원 BFS)

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

2206번: 벽 부수고 이동하기

 

이 문제의 경우, 벽을 부술 수 있는 기회 한 번이 주어진다.

테스트 케이스로 주어지지 않았지만 0,0 좌표에서 n-1,m-1 좌표까지 갈 때 벽을 부수지 않고 이동하는 최단 경로도 있다. 

나는 벽인 좌표들을 walls라는 배열에 넣어 벽을 하나씩 부숴가며 bfs를 돌려주었다.

하지만 한 번도 벽을 부수지 않고 이동하는 경우에 대해서는 검사하지 않았다.  

따라서 벽을 부수는 경우와 부수지 않는 경우를 3차원 배열 visited[x][y][z]을 이용하여 z 부분에 벽을 부쉈는지 안부쉈는지 체크하며 풀어 주었다. 

z = 0 일때 벽을 부수지 않은 경우

z = 1일때 벽을 부순 경우

 

[3차원 배열을 이용하여 통과한 코드]

from collections import deque

def bfs():
    global board, answer
    moves = [(1,0),(0,1),(-1,0),(0,-1)]
    deq = deque([(0, 0, 0)])
    visited = [[[0]*m for _ in range(n)] for _ in range(2)]
    visited[0][0][0] = 1
    while deq:
        x, y, z = deq.popleft()
        if x == n-1 and y == m-1:
            return visited[z][x][y]

        for dx, dy in moves:
            nx = dx + x
            ny = dy + y
            if 0 <= nx < n and 0 <= ny < m:
                # 벽이 아니고 방문하지도 않은 경우
                if not board[nx][ny] and not visited[z][nx][ny]:
                    visited[z][nx][ny] = visited[z][x][y] + 1
                    deq.append((nx, ny, z))
                # 벽인데 아직 부술 수 있는 기회가 남아있는 경우
                elif board[nx][ny] and z == 0:
                    visited[z + 1][nx][ny] = visited[z][x][y] + 1
                    deq.append((nx, ny, z+1))

    return 1e9


n, m = map(int, input().split())
board = [list(map(int, list(input()))) for i in range(n)]
answer = bfs()
print(-1 if answer == 1e9 else answer)

  

 

[실패한 코드]

from collections import deque


def bfs():
    global board, answer
    moves = [(1,0),(0,1),(-1,0),(0,-1)]
    deq = deque([(0, 0)])
    visited = [[0]*m for _ in range(n)]
    visited[0][0] = 1
    while deq:
        x, y = deq.popleft()
        if x == n-1 and y == m-1:
            return visited[x][y]
        for dx, dy in moves:
            nx = dx + x
            ny = dy + y
            if 0 <= nx < n and 0 <= ny < m:
                if not board[nx][ny] and not visited[nx][ny]:
                    visited[nx][ny] = visited[x][y] + 1
                    deq.append((nx, ny))

    return 1e9


n, m = map(int, input().split())
board, walls = [], []
answer = 1e9
for i in range(n):
    arr = list(map(int, list(input())))
    board.append(arr)
    for j in range(m):
        if board[i][j]:
            walls.append((i, j))

# 문제 --- 벽을 부수지 않는 경우를 처리하지 못함 fail
for x, y in walls:
    # 벽부수기
    board[x][y] = 0
    answer = min(answer, bfs())
    # 벽원래대로 되돌려 놓기
    board[x][y] = 1
    
print(-1 if answer == 1e9 else answer)