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

문제

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

진짜 작살나고 짜릿하게 어려웠던 문제다.
매일 실버만 풀다가 처음으로 도전한 골드문제였다.
🥊 골드한테 흠칫 뚜들겨 맞고, 🚑 브론즈 응급실 가서 수액 맞고 겨우 정신차렸다..

알고리즘 고수 멋쟁이(✨)한테 헬프 요청해서 겨우 풀었다 ㅠㅡㅠ

틀린 문제 풀이

처음에 접근했던 방법은 다음과 같다.

1. 출발지인 (0, 0) 을 방문했다고 체크를 해주고, queue에 (0,0,1,0)를 넣어준다. [ x, y, cnt, check ] 를 넣어준 것이다.
   이때 check는 벽을 부셨는지 안부셨는지 여부를 나타낸다.
   cnt는 한칸씩 이동한 횟수를 나타낸다.

2. queue에 들어온 좌표의 상하좌우 중 방문 안한 곳만 방문할 것이다.

   2-1. 만약 (nx,ny)가 벽이고, 벽을 부신적이 없으면 벽을 부시고 방문해준다.
   그리고 queue에 (nx, ny, cnt+1, 1)을 넣어준다.

   2-2. 만약 (nx,ny)가 길이면, queue에 (nx, ny, cnt+1, check)를 넣어준다.

3. queue에 들어온 좌표가 도착지이면 cnt를 return 한다.

이렇게 풀었는데 시간초과가 발생했다.
코드 상으로는 다 맞는 것 같은데 무엇이 문제인지 알 수가 없었다.

반례를 계속 찾아보다가 논리의 문제를 알게 되었다.

반례 🤦🏻‍♀️

5 4
0001
1101
0001
0111
0010

위의 예제같은 경우 출발지 (0,0) 에서 바로 밑에 있는 벽을 부시고 이동하는 것이 처음엔 최적의 해다.
그렇지만 나중에 도착지에 가선 벽을 하나 더 부셔야 한다.

따라서 처음에 벽을 부시지않고 옆쪽으로 돌아와서 마지막에 벽을 부셔야 한다.
지금의 코드로는 이러한 상황을 고려할 수 없었다.
따라서 벽을 부셨을 때와 부시지 않았을 때를 분리해서 방문을 체크해야 한다.

올바른 문제 풀이

기존의 visited[x][y]를 visited[check][x][y]로 바꾸어주었다.
벽을 부신 여부에 따라 다른 visited에 저장된다.

1. queue에 (0,0,1,0)를 넣어준다.
2. queue에 들어온 좌표의 상하좌우 중 방문 안한 곳 visited[check][nx][ny] == 0 만 방문할 것이다.
   2-0. 방문해준다.
   ➣ visited[check][nx][ny] = 1
   2-1. 만약 (nx,ny)가 벽이고, 벽을 부신적이 없으면 벽을 부신다.
   그리고 queue에 (nx, ny, cnt+1, 1)을 넣어준다.
   2-2. 만약 (nx,ny)가 길이면, queue에 (nx, ny, cnt+1, check)를 넣어준다.

코드

import sys
from collections import deque

input=sys.stdin.readline

n, m = map(int,input().rstrip().rsplit())
queue = deque()

matrix = []
visited = [[[0]*(m+1) for _ in range(n+1)] for _ in range(2) ]

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

for i in range(n):
    row = input().rstrip()
    matrix.append(row)

def bfs():
    queue.append([0,0,1,0])

    while queue:
        x,y,cnt,check = queue.popleft()

        if x == n-1 and y == m-1:
            return cnt

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                # 방문했으면 continue
                if visited[check][nx][ny] == 1:
                    continue
                #방문 안했으면
                else:
                    visited[check][nx][ny] = 1

                    #벽이면
                    if matrix[nx][ny] == '1':
                        #벽 부신적이 없으면, 부시고 방문해줘
                        if check == 0 :
                            queue.append([nx,ny,cnt+1,1])
                    #길이면
                    else:
                        queue.append([nx,ny,cnt+1,check])

    return -1

print(bfs())