[BOJ 2206] 벽 부수고 이동하기 (Python)

복습 요망!!

풀이

먼저 벽과 상관없이 (1, 1)에서 출발하여 (N, M)에 도착하였을 때 최단 경로를 BFS로 구현하였다. BFS로 탐색하면서 벽을 1번만 뚫을 수 있다는 조건을 구현하는 것이 어려웠다. 처음에는 벽을 뚫었는지 안뚫었는지를 저장하는 전역 변수를 만들어서 True, False로 표현했지만, 틀렸다. 반례를 인터넷에 찾아보니 아래와 같은 예제에서 통과하지 못하는 것을 알 수 있었다.

0 0 0 0
0 1 0 0
0 0 0 0
1 1 1 1
0 0 0 0

위 경우에 벽을 뚫지 않고도 최단 경로를 구할 수 있으나, 진하게 표시된 1을 먼저 부수고 온 경우 4행의 1 1 1 1 벽을 뚫지 못하게 된다. 따라서 visited 방문 리스트를 3차원 리스트로 만들어 벽을 뚫지않고 온 경우와 벽을 뚫고 온 경우를 표현했다. 문제의 포인트는 visited 방문 리스트를 3차원 리스트로 생성하는 것이라고 생각한다.

visited[r][c][0]에는 벽을 뚫지않고 온 경우의 최단 경로 횟수를 저장하고, visited[r][c][1]에는 벽을 1번만 뚫고 온 경우의 최단 경로 횟수를 저장한다. BFS 탐색 시 위와 같은 3차원 방문 리스트를 이용하면 (N, M)에 도착했을 때 최단 경로를 구할 수 있다.

코드

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
board = [list(map(int, input().rstrip())) for _ in range(N)]
visited = [[[0] * 2 for _ in range(M)] for _ in range(N)]
dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
ans = 0


def bfs():
    # (0, 0) 출발, 벽 안부순 상태 시작
    q = deque([(0, 0, 0)])
    visited[0][0][0] = 1

    while q:
        r, c, wall = q.popleft()
        if r == N - 1 and c == M - 1:
            return visited[r][c][wall]

        for i in range(4):
            nr = r + dir[i][0]
            nc = c + dir[i][1]
            # 맵 범위 안에 있고, 한 번도 방문하지 않았으면
            if 0 <= nr < N and 0 <= nc < M and visited[nr][nc][wall] == 0:
                # 벽이 아니라면 이동하고, 이전경로 + 1 visited 배열에 저장
                if board[nr][nc] == 0:
                    q.append((nr, nc, wall))
                    visited[nr][nc][wall] = visited[r][c][wall] + 1
                
                # 벽 1번도 안 부쉈고, 다음 이동할 곳이 벽이라면
                if wall == 0 and board[nr][nc] == 1:
                    # 벽을 부순 상태를 1로 표현
                    q.append((nr, nc, 1))
                    # 벽 부순 상태의 visited[nr][nc][1]에 이전경로 + 1 저장
                    visited[nr][nc][1] = visited[r][c][wall] + 1

    return -1


print(bfs())