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

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

2206번: 벽 부수고 이동하기

---

 

24/03/19

 

 

BFS 응용 문제로, 클래스에 있는 아주 교육적인 문제다. 한번 더 생각해야 되는 좋은 문제다.

---

 

문제 접근 방식:

 

 

기본적으로 최단 거리를 구해야 되는 문제이기 때문에 BFS를 사용해야겠다는 감은 올 것이다.

 

그러면 어떻게 BFS를 구현할 것이냐가 문제인데, 벽을 최대 한 칸까지 뚫을 수 있다는 점이 핵심이다.

 

따라서 벽을 뚫는 행위를 어떻게 구현할 것인가가 이 문제의 핵심이 될 것이다.

 

해결법은 벽을 뚫는 행위를 했는가 하지 않았는가의 두 가지 경우로 나누어서, 방문 배열을 따로 관리하는 것이다.

 

$(0, 0)$칸은 항상 벽이 없는 칸이라고 문제에서 제시되어 있으므로, 벽을 뚫는 행위를 하지 않은 경우의 방문 배열의 $(0, 0)$칸을 방문 처리하고 큐에 담으면 된다.

 

이후 BFS를 진행하는데, 케이스를 다음과 같이 분류할 수 있다.

 

1. 지금까지 벽을 뚫는 행위를 하지 않았고, 앞으로 방문할 칸이 빈 칸일 경우

2. 지금까지 벽을 뚫는 행위를 하지 않았고, 앞으로 방문할 칸이 벽일 경우

3. 이전에 벽을 뚫는 행위를 했었고, 앞으로 방문할 칸이 빈 칸일 경우

4. 이전에 벽을 뚫는 행위를 했었고, 앞으로 방문할 칸이 벽일 경우

 

$1$번 경우는 벽을 뚫는 행위를 하지 않고 그냥 다음 칸을 방문처리 할 수 있다. 벽을 뚫는 행위를 하지 않았을 때의 방문 배열에 방문 처리를 해주면 충분하다.

 

$2$번 경우는 벽을 뚫는 행위를 해야만 한다. 따라서 벽을 뚫었을 때의 방문 배열에 방문 처리를 해주면 된다.

 

$3$번 경우는 이미 내가 벽을 뚫는 행위를 했었으므로, 벽을 뚫었을 때의 방문 배열에 방문 처리를 해주면 된다.

 

$4$번 경우는 그 칸은 방문할 수 없다. 따라서 그냥 처리하지 않아도 충분하다.

 

이 $4$가지 경우를 고려하여 방문 배열에 적절히 방문처리를 해주며 BFS를 진행하면 된다.

 

나의 경우, 방문 배열을 $3$차원 배열로 설정하여 방문 배열의 인덱스에 몇 번 벽 뚫는 행위를 했는지를 알아보기 쉽도록 구현했다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2206번 벽 부수고 이동하기
# BFS
'''
접근 방법:
벽을 뚫었는지 뚫지 않았는지의 여부를 나타내는 변수를 하나 추가한다.
'''
import sys
input = sys.stdin.readline
from collections import deque

dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]
N, M = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(N)]
visited = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(2)]
queue = deque()
queue.append((0, 0, 0, 1))  # 벽 뚫기 사용 여부, 위치, 거리
visited[0][0][0] = 1
while queue:
    can_break, r, c, dist = queue.popleft()
    if r == N-1 and c == M-1:
        print(dist)
        break
    if can_break == 0:  # 벽 뚫기 사용 아직 안했으면
        for i in range(4):
            nr, nc = r+dr[i], c+dc[i]
            if 0 <= nr < N and 0 <= nc < M:
                if visited[0][nr][nc] == 0 and graph[nr][nc] == 0:
                    visited[0][nr][nc] = 1
                    queue.append((0, nr, nc, dist+1))
                if visited[1][nr][nc] == 0 and graph[nr][nc] == 1:
                    visited[1][nr][nc] = 1
                    queue.append((1, nr, nc, dist+1))
    else:  # 벽 뚫기를 이미 사용했다면
        for i in range(4):
            nr, nc = r+dr[i], c+dc[i]
            if 0 <= nr < N and 0 <= nc < M:
                if visited[1][nr][nc] == 0 and graph[nr][nc] == 0:
                    visited[1][nr][nc] = 1
                    queue.append((1, nr, nc, dist+1))
else:
    print(-1)