[백준/Python] 2206. 벽 부수고 이동하기

이러한 유형에 대해 더 깔끔하고 일반적인 풀이 방법을 발견해서 새로 포스팅을 작성하였다. 공부를 위해 현 포스팅을 읽어보는 것도 괜찮지만, 좀 더 일반적인 풀이를 담은 아래 포스팅을 추천한다.

[백준/Python] 2206. 벽 부수고 이동하기 - 3차원으로 풀기

---

이번 포스팅은 오답 풀이인 '✏️ 풀이 1'과 정답 풀이인 '✏️ 풀이 2', '✏️ 풀이 3'으로 3가지 코드가 정리되어있다.
'✏️ 풀이 2'와 '✏️ 풀이 3'는 같은 방식의 풀이라 거의 비슷하지만, '✏️ 풀이 2'는 조금 더 직관적이고 '✏️ 풀이 3'는 조금 더 깔끔한 정답 풀이이니 필요에 따라 참고하기 바란다.

---

📄 문제

백준
난이도 : Gold 3
문제 제목 : 벽 부수고 이동하기

✏️ 풀이 1 / 오답 / 메모리 초과

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
matrix = [list(map(int, list(input().strip()))) for _ in range(n)]

dy = (-1, 0, 0, 1)
dx = (0, -1, 1, 0)
def bfs():
    deq = deque([[0, 0, True, 1]])
    visited = [[0] * m for _ in range(n)]
    visited[0][0] = 1
    
    while deq:
        y, x, can_break, current_dist = deq.popleft()
        if y == n - 1 and x == m - 1:
            print(current_dist)
            sys.exit(0)
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or nx < 0 or ny >= n or nx >= m:
                continue
            if visited[ny][nx]:
                continue
            
            flag = True
            if not can_break:
                if matrix[ny][nx]:
                    continue
                flag = False
                deq.append([ny, nx, False, current_dist + 1])
            else:
                if matrix[ny][nx]:
                    flag = False
                deq.append([ny, nx, flag, current_dist + 1])

            if flag:
                visited[ny][nx] = 1
            
bfs()
print(-1)

✅ 풀이 한줄 설명:
큐(deq)에 저장되는 요소는 [{y 좌표}, {x 좌표}, {벽을 부술 수 있는지 여부}, {누적 거리}]로 구성된다.
큐(deq)에 저장된 요소를 하나씩 pop하고 루프를 돌 때, 해당 요소의 3번째 요소 즉 {벽을 부술 수 있는지 여부}에 따라 해당 경로가 이미 벽을 한 번 부순 경로인지 아닌지 나누어 진행한다.
만약 새로 큐(deq)에 넣는 요소가 3번째 요소로 False를 가진다면(벽을 부수고 가는 경로라면) visited[ny][nx]를 그대로 두어 방문 표시를 하지 않는다.

✅ 풀이 자세한 설명:
너무 길면 가장 마지막 '✨ 정리' 부분만 읽어봐도 괜찮다. 그러나 해당 부분을 읽고 코드를 봐도 이해가 안된다면 천천히 전체를 읽어보기 바란다.
사실 메모리 초과로 오답지만 뒤에 나올 정답 풀이들도 이 풀이에서 기반했으니 읽어봐도 좋을 것 같다.

🍎 문제 파악하기
우선 문제가 어떤 유형인지, 어떤 특이점이 있는지 파악한다.

1. 기본적으로 BFS 문제이다. 현재 위치에서 상하좌우 인접한 칸으로 이동할 수 있고, 0은 이동 가능한 곳, 1은 이동 불가능한 벽이라는 부분에서 BFS 문제임을 알 수 있다.
2. 특이점에 대해 정리한다. 일반적인 BFS와 달리 '벽을 한 개까지 부수고 이동할 수' 있다. 끝점까지의 최단거리를 구하는 문제로, 벽을 한 번 부순 경로가 최단 거리가 될 수도 있다.

🍎 특이점으로 인한 상황 파악하기
특이점이 있다면 그로 인해 고려해야 할 사항들을 파악한다.

1. 벽을 한 번 부순 경로는 또 다시 벽을 만나면 더 이상 이동할 수 없어 정답이 될 수 없다.
2. 벽을 부수지 않은 경로와 벽을 한 번 부순 경로는 중간에 경로가 겹칠 수 있다.
   1. 벽을 한 번 부순 경로 요소에서 인접 칸을 확인할 때:
      인접 칸이 이미 방문되었으면 해당 인접 칸으로 이동할 필요가 없다. 그 경로는 어차피 최단 거리가 아닐 것이기 때문이다.
   2. 벽을 부수지 않은 경로 요소에서 인접 칸을 확인할 때:
      인접 칸이 '벽을 부수지 않은 경로' 중 방문되었다면 일반적인 BFS와 같이 최단 거리가 아닐 것이기에 해당 인접 칸으로 이동할 필요가 없다.
      그러나 인접 칸이 '벽을 한 번 부순 경로' 중 방문되었다면 해당 인접 칸으로는 이동해봐야 한다.
      벽을 한 번 부순 경로는 이후에 또 벽을 만나면 사라질 경로이기 때문이다.

🍎 규칙 세우기
다음으로 규칙을 세운다.

1. 위의 '🍎 특이점으로 인한 상황 파악하기' 중 2번 사항으로 인해 '벽을 한 번 부순 경로'일 경우 visited에 방문 표시를 남기지 않는다.
2. 1번을 위해 '벽을 한 번 부순 경로'일 경우와 '벽을 부수지 않은 경로'일 경우를 일부 나누어서 처리한다.
3. 2번을 위해 deq에 요소를 저장할 때 [{y 좌표}, {x 좌표}, {벽을 부술 수 있는지 여부}, {누적 거리}]의 구성으로 저장한다.
4. 그 외는 일반적인 BFS 풀이를 이용한다.

✨ 정리
정리하자면 풀이 결과는 다음과 같다.

1. 기본적으로 BFS 문제 풀이이다. 그러나 '벽을 한 번 부순 경로'가 지나간 길을 '벽을 부수지 않은 경로'가 지날 수 있도록 해야하기 때문에 '벽을 한 번 부순 경로'는 visited에 방문 표시를 남기지 않는다.
2. 이를 위해 deq의 요소 구성은 [{y 좌표}, {x 좌표}, {벽을 부술 수 있는지 여부}, {누적 거리}]로 하고, 매 루프마다 현재 경로가 벽을 부순 경로인지 아닌지를 확인하여 각각 적절한 처리를 해준다.

🚫 오답 설명
해당 코드는 메모리 초과로 오답을 반환한다.
'벽을 한 번 부순 경로'일 경우 방문 표시를 하지 않아 인접 칸이 0이기만 하면 이미 갔던 칸도 deq에 추가하기 때문이다.

if flag:
	visited[ny][nx] = 1

이렇게 되면 끝점(도착 지점)에 도달하기 전까지 무수히 많은 요소가 deq에 추가되기 때문에 문제가 발생한다.
❗️ 해결 방법
'벽을 한 번 부순 경로'일 경우 '벽을 부수지 않은 경로'일 때와는 다른 마크로 방문 표시를 해준다. 자세한 내용과 적용 방법은 밑의 '✏️ 풀이 2'와 '✏️ 풀이 3'을 참고바란다.

✏️ 풀이 2

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
matrix = [list(map(int, list(input().strip()))) for _ in range(n)]

dy = (-1, 0, 0, 1)
dx = (0, -1, 1, 0)
def bfs():
    deq = deque([[0, 0, True, 1]])
    visited = [[0] * m for _ in range(n)]
    visited[0][0] = 1
    
    while deq:
        y, x, can_break, current_dist = deq.popleft()
        if y == n - 1 and x == m - 1:
            print(current_dist)
            sys.exit(0)
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or nx < 0 or ny >= n or nx >= m:
                continue
            
            if not can_break:
                if visited[ny][nx]:
                    continue
                if matrix[ny][nx]:
                    continue
                deq.append([ny, nx, False, current_dist + 1])
                visited[ny][nx] = 2
            else:
                flag = True
                if visited[ny][nx] == 1:
                    continue
                if matrix[ny][nx]:
                    flag = False
                deq.append([ny, nx, flag, current_dist + 1])
                visited[ny][nx] = 1 if flag else 2
            
bfs()
print(-1)

✅ 풀이 한줄 설명:
큐(deq)에 저장되는 요소는 [{y 좌표}, {x 좌표}, {벽을 부술 수 있는지 여부}, {누적 거리}]로 구성된다.
큐(deq)에 저장된 요소를 하나씩 pop하고 루프를 돌 때, 해당 요소의 3번째 요소 즉 {벽을 부술 수 있는지 여부}에 따라 해당 경로가 이미 벽을 한 번 부순 경로인지 아닌지 나누어 진행한다.
만약 새로 큐(deq)에 넣는 요소가 3번째 요소로 False를 가진다면(벽을 부수고 가는 경로라면) visited[ny][nx]를 2로, True를 가진다면(벽을 부수지 않고 가는 경로라면) visited[ny][nx]를 1로 하여 서로 다른 방문 표시를 둔다.

✅ 풀이 자세한 설명:

1. 기본적으로 BFS 문제 풀이이다. 일반적인 BFS와 같이 '벽을 부수지 않은 경로'는 visited에 1을 저장하여 방문 표식을 남긴다.
   그러나 '벽을 한 번 부순 경로'가 지나간 길을 '벽을 부수지 않은 경로'가 지날 수 있도록 해야하기 때문에 '벽을 한 번 부순 경로'는 visited에 2라는 다른 방문 표식을 남긴다.
2. 이를 위해 deq의 요소 구성은 [{y 좌표}, {x 좌표}, {벽을 부술 수 있는지 여부}, {누적 거리}]로 하고, 매 루프마다 현재 경로가 벽을 부순 경로인지 아닌지를 확인하여 아래와 같이 각각 적절한 처리를 해준다.

if not can_break:
	if visited[ny][nx]:
		continue
	if matrix[ny][nx]:
        continue
    deq.append([ny, nx, False, current_dist + 1])
    visited[ny][nx] = 2
else:
	flag = True
	if visited[ny][nx] == 1:
    	continue
	if matrix[ny][nx]:
		flag = False
    deq.append([ny, nx, flag, current_dist + 1])
	visited[ny][nx] = 1 if flag else 2
            

만약 벽을 이미 한 번 부셔서 더 이상 부술 수 없는 경우, visted가 1이거나 2이면 어차피 최단 거리가 아니기때문에 패스한다. matrix가 1이어도 더 이상 벽을 부술 수 없기 때문에 패스한다. 그 외에는 deq에 요소를 추가하고 visited에 벽을 부순 경로라는 의미로 2를 할당한다.
만약 벽을 부수지 않은 경우, visited가 1일 경우에만 최단 거리가 아니기 때문에 패스한다. 그리고 matrix가 1이면 벽을 부수고, 부쉈다는 의미로 flag = False로 바꾼다. 그 후 deq에 요소를 추가하는데 벽을 새로 부쉈으면 2번째 인덱스에 False, 아니면 True를 넣어준다. visited에는 벽을 새로 부쉈으면 2, 아니면 1을 할당한다.

✏️ 풀이 3

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
matrix = [list(map(int, list(input().strip()))) for _ in range(n)]

dy = (-1, 0, 0, 1)
dx = (0, -1, 1, 0)
def bfs():
    deq = deque([[0, 0, True, 1]])
    visited = [[0] * m for _ in range(n)]
    visited[0][0] = 1
    
    while deq:
        y, x, can_break, current_dist = deq.popleft()
        if y == n - 1 and x == m - 1:
            print(current_dist)
            sys.exit(0)
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or nx < 0 or ny >= n or nx >= m:
                continue

            if visited[ny][nx] == 1 or (visited[ny][nx] == 2 and not can_break):
                continue
            if matrix[ny][nx] == 0:
                deq.append([ny, nx, can_break, current_dist + 1])
                visited[ny][nx] = 1 if can_break else 2
                continue
            if not can_break:
            	continue
            deq.append([ny, nx, False, current_dist + 1])
            visited[ny][nx] = 2
            
bfs()
print(-1)

'✏️ 풀이 2'에서 일부 피드백 받아 수정한 코드이다. 전체적으로 '✏️ 풀이 2'와 같은 풀이 방식을 따르기 때문에 '✏️ 풀이 2' 정리 내용을 먼저 이해하고 보는 것을 추천한다.
바뀐 부분은 아래 코드 부분으로, bfs 함수 내 while문 안의 for문 중 일부 코드이다.

if visited[ny][nx] == 1 or (visited[ny][nx] == 2 and not can_break):
	continue
if matrix[ny][nx] == 0:
	deq.append([ny, nx, can_break, current_dist + 1])
	visited[ny][nx] = 1 if can_break else 2
	continue
if not can_break:
	continue
deq.append([ny, nx, False, current_dist + 1])
visited[ny][nx] = 2

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Gold) '2206. 벽 부수고 이동하기'
GitHub - [9강] BFS/응용문제 '2206. 벽 부수고 이동하기'