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

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

2206번: 벽 부수고 이동하기

 

 

1. 해결방법

일단 체감상 어떻게 해결해야할지 감은 오지만 조건을 맞추는데 어려워서 굉장히 많은 시간을 함께 보낸 문제이다. 
하지만 좋은 문제인 것 같다.

전형적인 BFS 문제이며 , 벽을 딱 한번 부술 수 있는 특징이 있는 문제이다.

방문 체크를 2차원으로 해버리면, 이미 벽을 부순 노드가 빈 공간을 방문하다가 이동할 수 없는 상황일 때, 다녀면 위치가 다 방문 체크가 되어버리기 때문에 다른 노드가 같은 곳을 방문해버릴 수 없는 반례가 있다

이를 해결하기 위해서는 2차원의 배열을 두 개 만들거나, 3차원 배열을 이용해서 벽을 부순 경우와 부수지 않은 경우를 나눠서 체크해야 한다.

즉, chk[z][y][z] 라고 표현하고, z는 1이 부순 경우와 0은 부수지 않은 경우이다.


1. 방문체크 배열을 3차원으로 만든다.
2. bfs를 탐색하면, ey 가 N - 1, ex 가 M -1 일 때, return 한다.
3. dy, dx로 방향을 나아가면서 유효성 검사를 한다.
4. maps이 1 (벽)인 상태와 cnt가 0(노드가 벽을 부수지 않은 경우) 일때, chk[1][ny][nx]가 기존의 위치보다 1을 증가시킨다.
5. 빈 공간일 경우, chk[cnt][ny][nx]는 기존의 위치에서 1을 증가만 시킨다.
6. q에 해당 인덱스 위치와 cnt 값을 append 한다.

 

 

 

2. 정답코드

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
maps = [list(map(int, input().strip())) for _ in range(N)]
chk = [[[False] * M for _ in range(N)] for _ in range(2)]

dy, dx = (1, -1, 0, 0), (0, 0, 1, -1)

def bfs(y, x):
    q = deque()
    q.append((y, x, 0))
    chk[0][y][x] = 1

    while q:
        ey, ex, cnt = q.popleft()

        if ey == N - 1 and ex == M - 1:
            return chk[cnt][ey][ex]

        for d in range(4):
            ny, nx = ey + dy[d], ex + dx[d]
            if 0 <= ny < N and 0 <= nx < M:
                # 벽일 경우와 벽을 깨부셔야 할 때,
                if maps[ny][nx] == 1 and cnt == 0:
                    chk[1][ny][nx] = chk[0][ey][ex] + 1
                    q.append((ny, nx, 1))
                elif maps[ny][nx] == 0 and chk[cnt][ny][nx] == 0:
                    chk[cnt][ny][nx] = chk[cnt][ey][ex] + 1
                    q.append((ny, nx, cnt))
    return -1


print(bfs(0, 0))