[백준] 2206 벽 부수고 이동하기 (Python/파이썬)

<문제 링크>

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

2206번: 벽 부수고 이동하기

<풀이 전략>

1. 벽을 부수는 걸 구현하는 게 핵심이다.
2. 일반적인 2차원 배열에 벽 부수는 걸 나타내주는 변수를 추가적으로 넣어서 bfs를 돌리면 에러가 난다.
   • 특정 지점 (r, c)에 벽을 부수고 도달하는 방법(a)랑 벽을 부수지 않고 도달하는 방법(b)가 있는데, a가 b보다 거리가 짧을 때(a < b)일 때 2차원 배열에서는 a만 표시 된다.
   • 그러다 나중에 벽을 부수지 않고는 통과하지 못하는 상황이 발생할 때 이미 벽을 부셨기 때문에(a) 통과를 못하고 -1을 반환하게 되는데, 사실 b 루트로 왔으면 통과할 수 있는 길이다.

3. 따라서 벽을 부수지 않은 배열과 벽을 부수지 않은 배열 두 배열을 담아서 3차원 배열로 표현하고 bfs를 돌려야 한다. 만화나 영화에서 선택에 따라 세계선이 나뉘는 그런 느낌으로 이해하면 된다.

4. 3차원 배열을 만들 때 주의해야할 점은 arr이 기본적으로 2차원 배열이기 때문에 할당이나 그냥 복사가 아니라 deepcopy를 이용한 깊은 복사를 해줘야 한다.

5. 여기까지 했으면 벽을 부셨을 때 차원이 이동하는 것만 신경써서 bfs를 구현해주면 된다.

 

<정답 코드>

# 220827 2206 벽 부수고 이동하기

# 정답코드

from collections import deque
from copy import deepcopy
import sys
intput = sys.stdin.readline

# N: 행의 개수, M: 열의 개수
N, M = map(int, input().split())

# arr: 맵, arr2: arr의 복사본 (2차원 배열이므로 deepcopy)
arr = [list(map(int, input())) for _ in range(N)]
arr2 = deepcopy(arr)
# arr_3d: 맵의 3차원 배열 (0: 벽 안 부숨, 1: 벽 부숨)
arr_3d = [arr, arr2]

# 탐색 방향
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]


# 3차원 bfs 함수 선언
def bfs(z, r, c):

    # 출발점 표시
    arr_3d[z][r][c] = 1
    
    # queue: 좌표를 담을 큐
    queue = deque()
    queue.append((z, r, c))
    
    while queue:
        z, r, c = queue.popleft()
        
        # 목표 지점 도착 시 거리 출력 후 반환
        if r == N - 1 and c == M - 1:
            print(arr_3d[z][r][c])
            return

        # 4방향 탐색
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            # 탐색 방향이 인덱스 범위를 벗어나지 않을 때
            if 0 <= nr < N and 0 <= nc < M:

                # 벽이 있을 경우
                if arr_3d[z][nr][nc] == 1:
                    # 아직 벽을 부수지 않았을 경우 벽을 부수고 벽을 부순 차원으로 넘어가서 탐색을 진행한다.
                    if z == 0:
                        arr_3d[1][nr][nc] = arr_3d[0][r][c] + 1
                        queue.append((1, nr, nc))
                
                # 벽이 없을 경우 현재 차원에서 그대로 탐색을 진행한다.
                elif arr_3d[z][nr][nc] == 0:
                    arr_3d[z][nr][nc] = arr_3d[z][r][c] + 1
                    queue.append((z, nr, nc)) 
    
    # 목표 지점에 도착하지 못했을 경우 -1 출력 후 반환
    print(-1)
    return

# bfs 탐색 실시
bfs(0, 0, 0)