[BOJ] 벽 부수고 이동하기

---

코드

import sys
from collections import deque
input = sys.stdin.readline

def bfs():
    q = deque()
    visited = [[[0,0] for _ in range(m)] for _ in range(n)]
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    q.append((0, 0, 0))    # (x, y, 거리, 이전에 벽을 부쉈는지 여부)
    visited[0][0][0] = 1
    
    while q:
        x, y, br = q.popleft()
            
        if x == n-1 and y == m-1:
            return visited[x][y][br]

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                # 아직 방문하지 않은 경우 (벽을 깨고 왔거나 깨지않고 온 경우를 모두 고려)
                if graph[nx][ny] == 0 and visited[nx][ny][br] == 0:
                    q.append((nx, ny, br))
                    visited[nx][ny][br] = visited[x][y][br] + 1
                # 벽이고, 아직 벽을 부수지 않은 경우
                elif graph[nx][ny] == 1 and br == 0:
                    q.append((nx, ny, 1))
                    visited[nx][ny][1] = visited[x][y][br] + 1
    return -1
            
        
n, m = map(int, input().split())
graph = [list(map(int, list(str(input().rstrip())))) for _ in range(n)]

print(bfs())

결과

풀이 방법

• BFS를 활용하는 문제이다.
• 벽을 한 번만 부술 수 있기 때문에, 이전에 벽을 부쉈는지 여부를 큐에 포함하여 BFS를 수행하도록 코드를 작성했지만 틀렸다.
• 틀린 이유는, 벽을 부순 여부를 체크해야 하는 것뿐만 아니라, 벽을 부수지 않고 온 경우와 벽을 부수고 온 경우의 최단거리를 각각 따로 계산해야 하기 때문이다.
• 따라서 벽이 아니고 아직 방문하지 않은 좌표인 경우에 대해, 벽을 부수고 온 경우에는 이전 좌표 visited[x][y]에서 벽을 부수고 왔을 때의 최단거리인 visited[x][y][1]을, 벽을 부수지 않고 온 경우에는 벽을 부수지 않고 왔을 때의 최단거리인 visited[x][y][0]을 참조하여 visited[x][y][벽을 부쉈는지 여부] 를 갱신해야 한다.
• 방문할 좌표가 벽이고, 아직 벽을 부수지 않은 경우에는, 벽을 부수게 되므로 vistied[nx][ny][1]에 이전 좌표에서 벽을 부수지 않고 왔을 때의 최단거리 visited[x][y][0]을 참조하여 갱신해야 한다.