[Python] boj no. 2206 : 벽 부수고 이동하기

Problem

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

Idea

최소 거리 문제이므로 너비 우선 탐색으로 해결했다. 이 때 한 개의 벽을 부술 수 있다는 조건이 있으므로 3차원 리스트를 이용해 벽 부수기 기회를 사용하지 않은 경우와 사용한 경우의 최단 거리를 각자 저장해주어야 한다. 따라서, 3차원 리스트는 visited[벽을 부쉈는가에 대한 여부][y 좌표][x 좌표]와 같이 선언되며 다음과 같은 경우 탐색이 가능하다.

1. 벽 부수기 기회를 사용하지 않았고 벽이 없는 지점으로 탐색하려는 경우
2. 벽 부수기 기회를 사용하지 않았고 벽이 있는 지점으로 탐색하려는 경우
3. 벽 부수기 기회를 사용하였고 벽이 없는 지점으로 탐색하려는 경우

벽 부수기 기회를 사용한 상황에서 벽이 있는 지점으로의 탐색은 벽 부수기 기회가 오직 1회뿐이므로 불가능하다.

Code

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
maze = [list(map(int, input().rstrip())) for _ in range(N)]
visited = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(2)]

queue = deque()
queue.append((0, 0, 0)) # y, x, wall break count
visited[0][0][0] = 1

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

sol = -1

while queue:
    cy, cx, cb = queue.popleft()
    
    if cy == N-1 and cx == M-1:
        sol = visited[cb][cy][cx]
        break
    
    for i in range(4):
        ny, nx = cy+dy[i], cx+dx[i]
        
        if ny < 0 or ny >= N or nx < 0 or nx >= M:
            continue
        
        if cb == 0:
            if maze[ny][nx] == 0 and visited[0][ny][nx] == 0:
                queue.append((ny, nx, 0))
                visited[0][ny][nx] = visited[cb][cy][cx] + 1
            elif maze[ny][nx] == 1 and visited[1][ny][nx] == 0:
                queue.append((ny, nx, 1))
                visited[1][ny][nx] = visited[cb][cy][cx] + 1
        else:
            if maze[ny][nx] == 0 and visited[1][ny][nx] == 0:
                queue.append((ny, nx, 1))
                visited[1][ny][nx] = visited[cb][cy][cx] + 1
        
print(sol)

Comment