BOJ 14442 · 벽 부수고 이동하기 2

알고리즘 분류 : BFS  

2206번 '벽 부수고 이동하기'를 변형한 문제다. 이전 문제는 벽을 최대 1개까지만 부술 수 있었으나, 이번 문제는 최대 10개까지 가능하다. 1개에서 10개로 늘어난 것이므로, 풀이는 비슷하게 접근할 수 있다. 이전 문제는 이곳에서 참조.

• dist 배열을 통해 방문 체크를 하고 이동 거리를 저장한다.
• dist는 3차원 배열이며, 인덱스는 [x좌표] [y좌표] [벽 부순 횟수] 이다.

---

C++ 소스코드

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

struct map {
    int x, y, w;
    // w is a flag for counting broken walls. 0(Unbroken) 1~10(Broken)
};

int n, m, k;
char a[1001][1001];
int dist[1001][1001][11];
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], nw = w+1;
            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' && nw <= k) {
                // Break the wall
                dist[nx][ny][nw] = dist[x][y][w] + 1;
                q.push({nx, ny, nw});
            }
        }
    }
    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)]
dist = [[[0]*(k+1) 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[n-1][m-1][w]
        for i in range(4):
            nx, ny, nw = x+dx[i], y+dy[i], w+1
            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 nw <= k:
                dist[nx][ny][nw] = dist[x][y][w] + 1
                q.append((nx, ny, nw))
    return -1

print(bfs())

✓ Python 3로 제출하면 시간 초과로 실패한다. 같은 코드를 PyPy3^[각주:1]로 제출하면 성공한다.

---

참고

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

1. PyPy는 Python 언어 구현 중 하나이다. 기존의 Python은 C로 쓰였지만, PyPy는 JIT 컴파일을 통해 Python으로 구현되었다. 즉, Python으로 만들어진 Python이다. 하지만, JIT 컴파일러 덕분에 CPython보다 성능이 더 좋다. 또한 Python을 그대로 호환한다. Python에서 되는 것이 PyPy에서 안 되면, 버그라고 생각하면 된다. [본문으로]