[백준] 2206번 벽 부수고 이동하기 ★★★

💡문제접근

• 좌표 개념의 문제고 최단거리라는 표현을 보자마자 BFS로 풀어야겠다고 생각했다. 근데 일반적인 최단거리 문제가 아니라 벽을 부술 수 있다는 특징을 가지고 있는 문제였다.
• 벽을 부수고 최단거리로 이동하는 방법도 존재하지만 벽을 부수지 않고 최단거리로 이동하는 방법도 존재한다. 이 부분을 어떻게 구현해야할지 막막해서 구글링을 했고 3차원 배열을 만들어서 하나는 벽을 부수지 않은 경우, 나머지 하나는 벽을 부수는 경우 두 가지로 나누어 탐색을 진행한다.
• visited[y][x][0]은 벽을 부순 경로, visited[y][x][1]은 벽을 부수지 않은 경로
• 만약 탐색을 진행하다가 중간에 벽을 부순 경로는 그 이후의 경로부터 벽을 부술 수 없기 때문에 벽이 아닌 곳들만 탐색하고 만약 탐색을 진행하다가 중간에 벽을 부수지 않은 경로는 그 이후의 경로에서 벽을 한 번만 부술 수 있다.

💡코드

# visited[y][x][0] : 벽을 부수고 이동하는 경우를 나타내는 방문 배열
# visited[y][x][1] : 벽을 부수지 않고 이동하는 경우를 나타내는 방문 배열
from collections import deque
import sys
input = sys.stdin.readline

def BFS(y, x, z):
    queue = deque()
    queue.append((y, x, z))
    while queue:
        a, b, c = queue.popleft()
        if a == N-1 and b == M-1:
            return visited[a][b][c]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4):
            nx = b + dx[i]
            ny = a + dy[i]
            # 영역 밖의 경우
            if ny < 0 or ny >= N or nx < 0 or nx >= M:
                continue
            # visited[y][x][0] : 벽을 부수고 이동하는 경우를 나타내는 방문 배열
            # visited[y][x][1] : 벽을 부수지 않고 이동하는 경우를 나타내는 방문 배열
            if 0 <= nx < M and 0 <= ny < N:
                # 해당 좌표가 벽이고 벽 파괴 기회를 사용하지 않은 경우
                if graph[ny][nx] == 1 and c == 0:
                    visited[ny][nx][1] = visited[a][b][c] + 1
                    queue.append((ny, nx, 1))
                # 해당 좌표가 벽이 아니고 방문하지 않은 곳이라면?
                elif graph[ny][nx] == 0 and not visited[ny][nx][c]:
                    visited[ny][nx][c] = visited[a][b][c] + 1
                    queue.append((ny, nx, c))
    return -1

N, M = map(int, input().strip().split())
visited = [[[0] * 2 for _ in range(M)] for _ in range(N)]
visited[0][0][0] = 1
graph = []
for _ in range(N):
    graph.append(list(map(int, input().strip())))
print(BFS(0, 0, 0))

💡소요시간 : 1d