BOJ 16933 · 벽 부수고 이동하기 3

알고리즘 분류 : BFS  

벽 부수고 이동하기 시리즈 세 번째 문제이다. 이번에는 이동할 때 낮과 밤이 매번 바뀌고, 낮에만 벽을 부술 수 있다.

BOJ 14442번 '벽 부수고 이동하기 2' 문제에서 낮과 밤 설정을 추가하여 구현하면 된다.

• check 배열을 통해 방문 여부 체크를 한다. 3차원 인덱스는 각각 [X 좌표] [Y 좌표] [벽 부순 횟수] 이다.
• 낮부터 시작하며, 큐에서 모든 좌표를 꺼낸 후에 낮과 밤을 바꾼다.

• 다음 이동 좌표가 빈칸(0)인 경우
• 1. 아직 방문하지 않은 곳이라면, 이동거리를 +1 증가시키고 이동한다.
• 2. 벽 부순 횟수는 업데이트하지 않는다.

• 다음 이동 좌표가 벽(1)인 경우
• 1. 벽 부순 횟수가 K 이하이며, 아직 방문하지 않은 곳이라면, 낮인지 밤인지 확인한다.
• 2. 낮인 경우, 벽을 부수고 이동할 수 있으므로, 벽 부순 횟수를 +1, 이동거리를 +1 증가시키고 이동한다.
• 3. 밤인 경우, 벽을 부술 수 없으므로, 이동거리만 +1 증가시키고 제자리에 있는다.

---

C++ 소스코드

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

struct wall {
    int x, y, w, d;
};

int n, m, k;
bool check[1000][1000][11];
char a[1001][1001];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int bfs() {
    queue<wall> q;
    q.push({0, 0, 0, 1});
    check[0][0][0] = true;
    bool day = true;
    while (!q.empty()) {
        int p = q.size();
        while (p--) {
            int x = q.front().x, y = q.front().y;
            int w = q.front().w, d = q.front().d; q.pop();
            if (x == n-1 && y == m-1) return d;
            for (int i=0; i<4; i++) {
                int nx = x+dx[i], ny = y+dy[i], nw = w+1, nd = d+1;
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (a[nx][ny] == '1' && !check[nx][ny][nw] && w < k) {
                    if (day) {
                        q.push({nx, ny, nw, nd});
                        check[nx][ny][nw] = true;
                    } else {
                        q.push({x, y, w, nd});
                    }
                }
                if (a[nx][ny] == '0' && !check[nx][ny][w]) {
                    q.push({nx, ny, w, nd});
                    check[nx][ny][w] = true;
                }
            }
        }
        day = !day;
    }
    return -1;
}

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

---

PyPy3 소스코드

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

n, m, k = map(int, input().split())
a = [list(input()) for _ in range(n)]
check = [[[False]*(k+1) for _ in range(m)] for _ in range(n)]

def bfs():
    q = deque()
    q.append((0, 0, 0, 1))
    check[0][0][0] = True
    day = True
    while q:
        p = len(q)
        for _ in range(p):
            x, y, w, d = q.popleft()
            if x == n-1 and y == m-1:
                return d
            for dx, dy in (-1,0), (1,0), (0,1), (0,-1):
                nx, ny, nw, nd = x+dx, y+dy, w+1, d+1
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                if a[nx][ny] == '1' and w < k and not check[nx][ny][nw]:
                    if day:
                        q.append((nx, ny, nw, nd))
                        check[nx][ny][nw] = True
                    else:
                        q.append((x, y, w, nd))
                if a[nx][ny] == '0' and not check[nx][ny][w]:
                    q.append((nx, ny, w, nd))
                    check[nx][ny][w] = True
        day = not day
    return -1

print(bfs())

✓ Python 3로 제출하면 시간 초과가 나오므로, PyPy3로 제출해야 한다.

---

참고

• 백준 온라인 저지 : BOJ 16933
• 벽 부수고 이동하기 2