BOJ 2206 · 벽 부수고 이동하기

알고리즘 분류 : BFS  

BFS를 통해 최단 거리를 구할 수 있는 문제다. 미로 탐색에서 약간 변형된 문제이며, 벽을 최대 1개만 부셔서 이동할 수 있다.

• 벽을 부수지 않거나(0), 벽을 1개 부시는(1) 경우로 나뉜다.
• 위의 경우를 확인하기 위해 flag를 만들고, 이를 Queue에 집어 넣는다.
• 다음 이동에서 벽을 만난 경우, flag가 0이면 벽을 부수고 flag를 1로 바꾼다.
• 방문 여부는 dist 배열로 체크하며, 값이 0이 아니면 방문한 곳이다.
• dist 배열은 3차원 배열이며, 인덱스는 [x 좌표] [y 좌표] [벽 부순 여부] 이다.
• 마지막 인덱스가 [0]이면 벽을 부수지 않고 (N, M)에 도착한 경우이고, [1]이면 벽을 한 번 부수고 (N, M)에 도착한 경우이다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
using namespace std;

struct map {
    int x, y, w;
    // w is a flag for checking to break wall. 0(Unbroken) 1(Broken)
};

int n, m;
char a[1001][1001];
int dist[1001][1001][2];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int bfs() {
    queue<map> q;
    q.push({0, 0, 0});
    dist[0][0][0] = 1;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y, w = q.front().w;
        q.pop();
        if (x == n-1 && y == m-1) return dist[x][y][w];
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (dist[nx][ny][w]) continue;
            if (a[nx][ny] == '0') {
                dist[nx][ny][w] = dist[x][y][w] + 1;
                q.push({nx, ny, w});
            }
            if (a[nx][ny] == '1' && w == 0) {
                // Break the wall, and turn on the flag to 1.
                dist[nx][ny][1] = dist[x][y][w] + 1;
                q.push({nx, ny, 1});
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) scanf("%s", a[i]);
    printf("%d\n", bfs());
    return 0;
}

---

Python 3 소스코드

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

n, m = map(int, input().split())
a = [list(input()) for _ in range(n)]
dist = [[[0, 0] for _ in range(m)] for _ in range(n)]
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

def bfs():
    q = deque()
    q.append((0, 0, 0))
    dist[0][0][0] = 1
    while q:
        x, y, w = q.popleft()
        if x == n-1 and y == m-1:
            return dist[x][y][w]
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if dist[nx][ny][w]:
                continue
            if a[nx][ny] == '0':
                dist[nx][ny][w] = dist[x][y][w] + 1
                q.append((nx, ny, w))
            if a[nx][ny] == '1' and w == 0:
                dist[nx][ny][1] = dist[x][y][w] + 1
                q.append((nx, ny, 1))
    return -1

print(bfs())

---

참고

• 백준 온라인 저지 : BOJ 2206
• 미로 탐색