PS Featured

[PS] BOJ 2206 / 벽 부수고 이동하기

Minjun Kim

14 Dec 2025 • 8 min read

Thumbnail: Photo by Belinda Fewings (Unsplash)

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

풀이

우선순위 큐 기반의 BFS

최단 경로의 길이만 구하면 되므로, 거리를 우선순위로 하는 큐를 활용해 BFS(너비 우선 탐색)를 진행했습니다. 기본적인 틀은 벽을 부수지 못하는 경우의 BFS와 동일합니다.

from heapq import heappop, heappush

maze = [list(map(int, list(input().rstrip()))) for _ in range(N)] # 맵 입력
visited = [[[False] for _ in range(M)] for _ in range(N)] # 각 칸의 방문 여부를 기록한다.

pq = [(1, 0, 0)] # 우선순위 큐
visited[0][0] = True # 출발지점은 항상 방문 처리한다.

while pq:
    dist, r, c = heappop(pq)
    if r == N-1 and c == M-1: # 종점에 도달한 경우.
        # 거리 값을 우선순위로 사용했으므로, 항상 최단경로에 해당하는 경우부터 조건문에 도달하게 된다.
        print(dist)
        break

    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr = r + dr
        nc = c + dc
        # 다음 칸이 미로의 범위 안에 있고 아직 방문하지 않았을 때
        if 0 <= nr < N and 0 <= nc < M not visited[nr][nc]:
            if maze[nr][nc] == 0: # 벽이 아닌 곳을 만난 경우.
                visited[nr][nc] = True
                heappush(pq, (dist + 1, nr, nc))
else:
    print(-1)

우선순위 큐 기반의 BFS의 기본 구현

벽을 한 번 부술 수 있는 BFS

이제, 벽을 한 번 부수고 탐색할 수 있도록 위 코드를 수정해야 합니다.

탐색 과정에서, 기존에 기억하고 있던 정보는 다음과 같습니다.

현재 위치까지 탐색해 온 경로의 길이
현재 위치 (행, 열 번호)

벽을 한 번만 부수고 탐색할 수 있으므로, 벽을 부술 수 있는 상태인지 bool 타입으로 기록해 탐색 과정에서 참고했습니다.

추가로, 방문 여부를 단순히 bool타입으로 기록하기보다 방문할 때의 거리를 기록하도록 변경했습니다.

INF = N * M + 1
maze = [list(map(int, list(input().rstrip()))) for _ in range(N)]
visited = [[INF for _ in range(M)] for _ in range(N)] # 각 칸의 방문 여부를 기록한다.

pq = [(1, 0, 0, True)] # (이동한 거리, r, c, 벽을 부쉈는지의 여부)로 저장한다. 이동한 거리에는 출발 및 도착지점이 모두 포함되어야 하므로 초기값은 1이다.
visited[0][0] = 1 # 출발지점은 항상 벽이 아니므로, 벽을 부수지 않은 상태로 방문 처리한다.

while pq:
    dist, r, c, can_break = heappop(pq)
    if r == N-1 and c == M-1: # 종점에 도달한 경우.
        # 거리 값을 우선순위로 사용했으므로, 항상 최단경로에 해당하는 경우부터 조건문에 도달하게 된다.
        print(dist)
        break

    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr = r + dr
        nc = c + dc
        # 다음 칸이 미로의 범위 안에 있고 / 아직 방문하지 않았거나, 이전에 방문했던 경우보다 더 짧은 거리로 도달한 경우
        if 0 <= nr < N and 0 <= nc < M and dist + 1 < visited[nr][nc]:
            if maze[nr][nc] == 1 and can_break: # 벽을 부술 수 있는 상태에서 벽을 만난 경우.
                visited[nr][nc] = dist + 1
                heappush(pq, (dist + 1, nr, nc, False))
            elif maze[nr][nc] == 0: # 벽이 아닌 곳을 만난 경우.
                visited[nr][nc] = dist + 1
                heappush(pq, (dist + 1, nr, nc, can_break))
else:
    print(-1)

벽을 한 번 부술 수 있는 BFS (초안)

반례 처리하기

위 코드는 일부 경우에서 잘못된 답을 계산합니다. 간단한 반례를 하나 소개하겠습니다.

Input
4 5
00101
00010
11100
11110

Answer
8

위 코드의 경우, (2, 2)에서 (2, 3)으로 벽을 부수지 않고 갈 수 있는 경로가 존재함에도 이전에 먼저 방문한 것으로 처리되어 답을 찾지 못합니다. 따라서, 방문 처리에 단순히 거리 값만 사용하지 않고 추가적인 정보를 더해줘야 합니다.

visited배열을 수정해, (거리, 아직 문을 부술 수 있는지)의 2가지 정보를 기억하도록 개선했습니다.

이후, 새 노드를 방문할 때 이전보다 짧은 거리로 방문하는 경우 이외에도 이전에 벽을 부숴서 도달했지만 새로 탐색할 때 벽을 부수지 않고 도달했을 경우도 탐색을 이어가도록 수정했습니다. 비록 거리는 이전보다 더 길 수 있으나, 이전에는 벽을 더 부술 수 없어 탐색이 막힌 경우가 있을 수 있기 때문에 재탐색하기로 했습니다.

visited = [[[INF, True] for _ in range(M)] for _ in range(N)] # 각 칸의 방문 여부 및 벽을 아직 부술 수 있는 지 기록한다.

visited[0][0] = [1, True] # 출발지점은 항상 벽이 아니므로, 벽을 부수지 않은 상태로 방문 처리한다.

// 다른 변수들은 기존과 동일하다.

while pq:
    dist, r, c, can_break = heappop(pq)
    if r == N-1 and c == M-1: # 종점에 도달한 경우.
        # 거리 값을 우선순위로 사용했으므로, 항상 최단경로에 해당하는 경우부터 조건문에 도달하게 된다.
        print(dist)
        break

    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr = r + dr
        nc = c + dc
        # 다음 칸이 미로의 범위 안에 있고 / 아직 방문하지 않았거나, 이전에 방문했던 경우보다 더 짧은 거리로 도달한 경우 / 또는 이전에 벽을 부수고 도달했으나 이번에 벽을 부수지않고 도달했다면
        if 0 <= nr < N and 0 <= nc < M and (dist + 1 < visited[nr][nc][0] or (can_break and not visited[nr][nc][1])):
            if maze[nr][nc] == 1 and can_break: # 벽을 부술 수 있는 상태에서 벽을 만난 경우.
                visited[nr][nc][0] = dist + 1
                visited[nr][nc][1] = False # 이후 경로에서는 더 이상 벽을 부술 수 없다.
                heappush(pq, (dist + 1, nr, nc, False))
            elif maze[nr][nc] == 0: # 벽이 아닌 곳을 만난 경우.
                visited[nr][nc][0] = dist + 1
                visited[nr][nc][1] = can_break # 이후 경로에서 벽을 부술 수 있는지 기록
                heappush(pq, (dist + 1, nr, nc, can_break))
else:
    print(-1)

수정한 BFS 코드

전체 코드

from heapq import heappop, heappush
input = open(0).readline
N, M = map(int, input().split())

INF = N * M + 1
maze = [list(map(int, list(input().rstrip()))) for _ in range(N)]
visited = [[[INF, True] for _ in range(M)] for _ in range(N)] # 각 칸의 방문 여부 및 벽을 아직 부술 수 있는 지 기록한다.

pq = [(1, 0, 0, True)] # (이동한 거리, r, c, 벽을 부쉈는지의 여부)로 저장한다. 이동한 거리에는 출발 및 도착지점이 모두 포함되어야 하므로 초기값은 1이다.
visited[0][0] = [1, True] # 출발지점은 항상 벽이 아니므로, 벽을 부수지 않은 상태로 방문 처리한다.

while pq:
    dist, r, c, can_break = heappop(pq)
    if r == N-1 and c == M-1: # 종점에 도달한 경우.
        # 거리 값을 우선순위로 사용했으므로, 항상 최단경로에 해당하는 경우부터 조건문에 도달하게 된다.
        print(dist)
        break

    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr = r + dr
        nc = c + dc
        # 다음 칸이 미로의 범위 안에 있고 / 아직 방문하지 않았거나, 이전에 방문했던 경우보다 더 짧은 거리로 도달한 경우 / 또는 이전에 벽을 부수고 도달했으나 이번에 벽을 부수지않고 도달했다면
        if 0 <= nr < N and 0 <= nc < M and (dist + 1 < visited[nr][nc][0] or (can_break and not visited[nr][nc][1])):
            if maze[nr][nc] == 1 and can_break: # 벽을 부술 수 있는 상태에서 벽을 만난 경우.
                visited[nr][nc][0] = dist + 1
                visited[nr][nc][1] = False # 이후 경로에서는 더 이상 벽을 부술 수 없다.
                heappush(pq, (dist + 1, nr, nc, False))
            elif maze[nr][nc] == 0: # 벽이 아닌 곳을 만난 경우.
                visited[nr][nc][0] = dist + 1
                visited[nr][nc][1] = can_break # 이후 경로에서 벽을 부술 수 있는지 기록
                heappush(pq, (dist + 1, nr, nc, can_break))
else:
    print(-1)

solution.py