[BOJ] 14442번: 벽 부수고 이동하기 2

https://www.acmicpc.net/problem/14442

전형적인 BFS에 벽 부술 수 있는 조건을 붙인 문제이다. 보통 이런 문제들은 visit 배열을 visit[x][y][cnt]로 정의해서 구할 수 있다.

이런 건 코드를 보면서 할 게 나을 것 같다.

if (Map[nxtX][nxtY] == '0' && vst[nxtX][nxtY][now.cnt] == INF) {
    vst[nxtX][nxtY][now.cnt] = vst[now.x][now.y][now.cnt] + 1;
    Q.push({ nxtX, nxtY, now.cnt });
}
else if (now.cnt + 1 <= K && Map[nxtX][nxtY] == '1' && vst[nxtX][nxtY][now.cnt + 1] == INF) {
    vst[nxtX][nxtY][now.cnt + 1] = vst[now.x][now.y][now.cnt] + 1;
    Q.push({ nxtX, nxtY, now.cnt + 1});
}

이동할 수 있고 방문하지 않았다면 보통의 BFS처럼 해주고 벽인데 부술 수 있다면 한 번 부셔보는 작업을 하는 거다.

이런 문제들은 한 번 어떻게 짜는 지 보고 잘 기억하고 써먹는게 좋은 학습 방법인 것 같다. 무작정 붙잡고 있는 것보다 효율이 좋을 것 같다.

 

(N, M)까지 가는데 벽을 몇 번 부셔서 가는게 이득인지 모르기 때문에 마지막에 순회하면서 최소값을 찾아야 한다.

 

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

struct edg {
    int x, y, cnt;
};

const int dx[] = { -1, 1, 0, 0 }, dy[] = { 0,0,-1,1 }, INF = 1061109567;
int N, M, K;
char Map[1001][1001];
int vst[1001][1001][11];

int main()
{
    memset(vst, 0x3f, sizeof vst);
    scanf("%d %d %d", &N, &M, &K);
    for (int i = 0; i < N; ++i) scanf("%s", Map[i]);

    vst[0][0][0] = 1;
    queue<edg> Q;
    Q.push({ 0, 0, 0 });
    while (!Q.empty()) {
        auto now = Q.front();
        Q.pop();
        if (now.x == N - 1 && now.y == M - 1) break; 
        
        for (int i = 0; i < 4; ++i) {
            int nxtX = now.x + dx[i], nxtY = now.y + dy[i];

            if (0 > nxtX || nxtX >= N || 0 > nxtY || nxtY >= M) continue;

            if (Map[nxtX][nxtY] == '0' && vst[nxtX][nxtY][now.cnt] == INF) {
                vst[nxtX][nxtY][now.cnt] = vst[now.x][now.y][now.cnt] + 1;
                Q.push({ nxtX, nxtY, now.cnt });
            }
            else if (now.cnt + 1 <= K && Map[nxtX][nxtY] == '1' && vst[nxtX][nxtY][now.cnt + 1] == INF) {
                vst[nxtX][nxtY][now.cnt + 1] = vst[now.x][now.y][now.cnt] + 1;
                Q.push({ nxtX, nxtY, now.cnt + 1});
            }
        }
    }

    int ret = INF;
    for (int i = 0; i <= K; ++i) {
        ret = min(ret, vst[N - 1][M - 1][i]);
    }
    printf("%d\n", ret == INF ? -1 : ret);
    return 0;
}

 

업데이트 - 2022년 5월 25일

계정을 새로 바꾸면서 다시 문제를 풀어봤다. 다른 사람들에 비해 내 코드가 너무 느려서 빠르신 분들의 코드를 쭉 보니 3차원 배열을 쓰지 않고 풀지 않던가? 그래서 약간 분석을 해봤다. 그들의 방식은 BFS 트리의 깊이는 따로 관리해주면서 visit 배열 대신 벽을 몇 번 부쉈는지 확인하는 이차원 배열을 만들었다 (b[i][j]라고 하자).

배열 b를 활용해서 푸는 방법은 다익스트라에서 길이 업데이트하는 것과 비슷한 느낌이다. 작업 전에 b 배열은 K보다 큰 수로 초기화 시켜주고, b[curY][curX] + [1 또는 0] < b[nextY][nextX]일 때만 (nextY, nextX)를 큐에 넣어주면 된다.

#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int y, x;
};

int N, M, K;
int bcnt[1000][1000]; // break count
char map[1000][1001];

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        cin >> map[i];
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            bcnt[i][j] = 100; // arbitrary num. > 10
        }
    }

    const int dy[] = { -1, 0, 1, 0 };
    const int dx[] = { 0, 1, 0, -1 };

    queue<Node> q;
    bcnt[0][0] = 0;
    q.push({ 0, 0 });
    int depth = 1;

    while (!q.empty()) {
        int qSize = q.size();
        while (qSize--) {
            auto cur = q.front();
            int cx = cur.x, cy = cur.y;
            q.pop();

            if (cx == M - 1 && cy == N - 1) {
                cout << depth;
                return 0;
            }

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i], ny = cy + dy[i];

                if (nx < 0 || nx >= M || ny < 0 || ny >= N)
                    continue;

                if (map[ny][nx] == '1' && bcnt[cy][cx] < K && bcnt[cy][cx] + 1 < bcnt[ny][nx]) {
                    q.push({ ny, nx });
                    bcnt[ny][nx] = bcnt[cy][cx] + 1;
                } else if (map[ny][nx] == '0' && bcnt[cy][cx] < bcnt[ny][nx]) {
                    q.push({ ny, nx });
                    bcnt[ny][nx] = bcnt[cy][cx];
                }
            }
        }
        depth++;
    }

    cout << -1;

    return 0;
}