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

문제 링크 : https://www.acmicpc.net/problem/2206

알고리즘 유형 : BFS, 다이나믹 프로그래밍

(생각의 흐름)

1. 그래프를 완전 탐색 해야되고, 최단 경로를 찾아야 되니까 DFS 보단 BFS 가 어울린다.

2. 벽을 한 번 부숴도 되는데 이걸 어떻게 처리할까. BFS 의 큐에 벽을 부쉈는지 여부를 추가해야된다.

3. visit 은 3차원 테이블로 구성한다.
   • visit[x][y][0] = 벽을 아직 부순 적 없는 상태로 (x, y) 를 방문
   • visit[x][y][1] = 벽을 부순 상태로 (x, y) 를 방문
   • 이렇게 따로 처리하지 않을 경우 발생하는 예외가 있다.

• visit 을 2차원 테이블로 구성한다면 발생하는 예외.
  • (a, b) 라는 점에 도달하는 경로가 다음과 같이 2가지 있다고 했을 때.
  • (경로 1) = 벽을 한 번 부순적 있는 상태로 (a, b) 에 도달.
  • (경로 2) = 벽을 부순적 없는 상태로 (a, b) 에 도달.
  • 만약 (경로 1)이 먼저 큐에 들어가서 (a, b)의 방문 처리가 완료 되버린다면, (경로 2)의 방법으로는 한번 더 벽을 부술 수 있음에도 불구하고, (경로 2) 를 사용할 수 없게 된다.

파이썬 코드

from collections import deque
import sys
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
N, M = map(int, sys.stdin.readline().split())
graph = []
visit = [[[False, False] for _ in range(M)] for _ in range(N)]

for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().strip())))

q = deque()
q.append((0, 0, 1, 0))
# (x, y) 를 벽을 이미 한 번 부순 상태로 방문했으면 visit[x][y][1] = True
# (x, y) 를 벽을 아직 부순적 없는 상태로 방문했으면 visit[x][y][0] = True
visit[0][0][0] = True
can_reach = False
answer = 0

while q:
    x, y, dist, wall = q.popleft()

    if x == N-1 and y == M-1:
        can_reach = True
        answer = dist
        break

    for d in direction:
        nx = x + d[0]
        ny = y + d[1]
        if not(0 <= nx < N and 0 <= ny < M):
            continue

        if wall == 0 and not visit[nx][ny][0]:
            if graph[nx][ny] == 0:
                q.append((nx, ny, dist+1, wall))
            elif graph[nx][ny] == 1:
                q.append((nx, ny, dist+1, wall + 1))
            visit[nx][ny][0] = True

        elif wall == 1 and not visit[nx][ny][1]:
            if graph[nx][ny] == 0:
                q.append((nx, ny, dist+1, wall))
                visit[nx][ny][1] = True
            elif graph[nx][ny] == 1:
                continue


if not can_reach:
    print(-1)
else:
    print(answer)