백준 2206번 - 벽 부수고 이동하기

벽 부수고 이동하기 문제 바로 가기

풀이 날짜: 2026-04-11

baekjoon 알고리즘 문제 풀이

풀이 코드


from collections import deque

n,m = map(int,input().split())
graph = [list(map(int,input().strip())) for _ in range(n)]
visited = [[[0]*2 for _ in range(m)] for _ in range(n)]    

dx = [0,0,-1,1]
dy = [-1,1,0,0]

def bfs():
    q = deque()
    q.append((0,0,0))
    visited[0][0][0] = 1

    while q:
        x,y,broken = q.popleft()

        if x == n-1 and y == m-1:
            return visited[x][y][broken]
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 0 and visited[nx][ny][broken] == 0:
                    visited[nx][ny][broken] = visited[x][y][broken] + 1
                    q.append((nx,ny,broken))
                
                elif graph[nx][ny] == 1 and visited[nx][ny][1] == 0 and broken == 0:
                    visited[nx][ny][1] = visited[x][y][broken] + 1
                    q.append((nx,ny,1))
    return -1
print(bfs())

문제 이해

이 문제는 N × M 격자 형태의 지도에서 시작점 (0,0)에서 도착점 (N-1,M-1)까지 이동할 때의 최단 경로 길이를 구하는 문제이다. 이동은 상하좌우 네 방향으로만 가능하며, 지도에는 빈 칸(0)과 벽(1)이 존재한다.

특이한 조건은 벽을 최대 한 번만 부술 수 있다는 점이다. 즉, 이동 중에 단 한 번 벽을 통과할 수 있으며 그 이후에는 더 이상 벽을 부술 수 없다.

따라서 단순한 BFS로 해결할 수 있는 문제처럼 보이지만, 벽을 부쉈는지 여부에 따라 동일한 칸이라도 상태가 달라진다는 점을 고려해야 했다.

접근 방법

이 문제는 최단 거리를 구하는 문제이기 때문에 BFS(Breadth First Search)를 사용하는 것이 적절하다. 하지만 일반적인 BFS와 다른 점은 벽을 부쉈는지 여부라는 추가 상태가 존재한다는 것이다.

예를 들어 (x,y) 위치에 도착했다고 하더라도

아직 벽을 부수지 않고 도착한 경우
이미 벽을 한 번 부수고 도착한 경우 이 두 상황은 이후 이동 가능성이 달라진다. 따라서 같은 좌표라도 서로 다른 상태로 취급해야 한다.

이를 위해 방문 배열을 3차원 형태로 관리했다.

visited[x][y][0] → 벽을 부수지 않고 (x,y)에 도착한 경우
visited[x][y][1] → 벽을 한 번 부수고 (x,y)에 도착한 경우

BFS 탐색

BFS는 (x, y, broken) 상태를 큐에 넣어 탐색을 진행한다.

여기서 broken은 벽을 부쉈는지 여부를 의미한다.

0 → 아직 벽을 부수지 않음
1 → 이미 벽을 한 번 부숨

탐색 과정에서 다음 칸 (nx, ny)에 대해 다음과 같은 규칙을 적용했다.

다음 칸이 빈 칸(0)이라면 현재 상태를 유지한 채 이동한다.
다음 칸이 벽(1)이라면 아직 벽을 부수지 않은 경우에만 벽을 부수고 이동한다.

이때 BFS 특성상 먼저 도착하는 경로가 항상 최단 거리이기 때문에 도착 지점에 처음 도달했을 때의 거리를 반환하면 된다.

핵심 포인트!

방문 배열을 3차원으로 관리해야 한다.

같은 좌표라도 벽을 부쉈는지 여부에 따라 이후 탐색 가능성이 달라지기 때문이다.
BFS 큐에 (x,y,broken) 상태를 함께 저장해야 한다.

그래야 현재 상태에서 벽을 부술 수 있는지 여부를 판단할 수 있다.

미세먼지 확산을 구현할 때 중요한 점

핵심은 기존 배열 graph를 바로 수정하면 안 된다는 점이다. 이유는 현재 칸의 먼지가 확산되는 도중에, 이미 확산된 값이 다른 칸의 계산에 섞이면 안 되기 때문이다. 문제에서는 모든 미세먼지가 동시에 퍼지는 것처럼 처리해야 하므로, 새로운 배열 temp를 만들어 확산 결과를 따로 저장해야 한다.

각 칸에 대해 graph[x][y] > 0이면 미세먼지가 있다는 뜻이므로 확산을 시도한다. 이때 확산되는 양은 graph[x][y] // 5이며, 네 방향 중 실제로 확산 가능한 방향 수를 세기 위해 count 변수를 사용한다. 확산 가능한 방향은 격자 범위 안이면서 공기청정기 칸이 아닌 경우이다. 가능한 방향으로는 temp[nx][ny] += dust를 해주고, 몇 방향으로 퍼졌는지를 count에 누적한다. 마지막에는 원래 칸에 남아 있어야 할 먼지 양, 즉 원래 먼지 - (퍼져나간 양)을 temp[x][y]에 더해준다.

이 과정에서 내가 새롭게 이해한 점은, 시뮬레이션 문제에서는 현재 상태와 다음 상태를 섞지 않는 것이 매우 중요하다는 것이다. temp 배열은 단순한 임시 저장소가 아니라, 동시성을 코드로 구현하기 위한 장치라고 볼 수 있다.

회고

이 문제는 단순한 BFS 문제가 아니라 상태를 확장한 BFS 문제라는 점이 핵심이다. 특히 같은 위치라도 이전에 어떤 행동을 했는지에 따라 상태가 달라질 수 있다는 점을 이해하는 것이 중요했다.

이러한 유형은 코딩 테스트에서 자주 등장하며, 대표적으로

벽을 한 번만 부술 수 있는 미로 문제
특정 능력을 한 번만 사용할 수 있는 이동문제 등에서 동일한 패턴이 사용된다. 따라서 좌표 뿐만 아니라 추가 상태까지 함께 관리하는 방법을 익혀 두는 것이 중요하다고 생각하게 되었다.

Vienna sausage