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

문제

벽 부수고 이동하기

---

문제 해설

벽을 단 하나만 부수거나 부수지 않고 이동하여 최단 거리를 구하는 문제입니다.

BFS로 푸시려면 벽을 부순 여부와 x,y좌표를 큐에 담아 푸시면됩니다. 일반적인 BFS와 다른 것은 방문여부 체크 리스트를 단순히 boolean 형태로 저장하면 안된다는 것입니다.

왜냐하면 벽 뚫고 지나갔는데 그 지점이 이미 벽을 안뚫고 지나간적이 있다면 최단 거리가 아닙니다. 또, 이미 벽을 뚫고 지난 지점을 벽을 안뚫고 지나갈 수 있기 때문입니다.

보시는 바와 같이 벽을 뚫었을때의 최단 경로와 벽을 안뚫었을때의 최단 경로가 겹칠 수 있기 때문에 방문체크를 따로 해주어야 합니다.

저는 아직 도달하지 못했을때 0, 벽을 뚫고 도달했을때 1, 벽을 안뚫고 도달했을때 2로 놓았습니다.

---

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline
# bfs, dfs 둘다 가능할 것 같다.
n, m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
# visited 0 = 아예 지나간적 없음 1 = 벽 뚫고 지나간적 있음 2 = 벽 안뚫고 지나감
visited = [[0] * m for _ in range(n)]
answer = 1

# x,y,벽뚫 여부
visited[0][0] = 2
q = deque()
q.append((0, 0, False))
dx = -1, 0, 1, 0
dy = 0, 1, 0, -1
while q:
    size = len(q)
    for _ in range(size):
        x, y, broken = q.popleft()
        if x == n - 1 and y == m - 1:
            print(answer)
            exit()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 벽을 아직 안 부순 상태.
            if not broken and visited[nx][ny] < 2:
                # 벽을 부수고 이동
                if graph[nx][ny] == 1:
                    visited[nx][ny] = 2
                    q.append((nx, ny, True))
                # 벽을 안부수고 이동
                else:
                    visited[nx][ny] = 2
                    q.append((nx, ny, False))

            # 벽 부순 상태일 때, 오로지 방문하지 않았던 곳만 이동 가능.
            elif broken and visited[nx][ny] == 0 and graph[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append((nx, ny, True))
    answer += 1
print(-1)

---