[백준] 14443번 벽 부수고 이동하기 2 (2차원 배열)

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

 

해설

검색을 통해 찾는 대부분의 풀이는 3차원 배열을 사용하여 해결

벽을 부순 개수에 따른 2차원의 방문 여부를 체크하는 배열은

 벽을 부순 개수가 다르면 서로 독립적이므로 불필요한 탐색과정이 발생

이를 해결하기 위해 2차원 배열의 조건을 까다롭게 설정하여 이를 해결

결과적으로 이전의 방식보다 메모리와 시간에서 최적화 성공

 

조건

먼저 BFS는 물 파동과 같이 퍼져나간다는 것을 이해해야 합니다. 

어떤 지점이 이미 이전 큐의 값에 의해 도달되었다면, 이후의 값들은 무조건 이전 큐의 값보다 느리기 때문에 무시 가능합니다.

하지만 이 문제에서는 벽을 부순 개수라는 새로운 조건이 추가되었습니다. 

이를 곰곰히 생각해보면, 예를 들어, 벽을 1개 부순 queue 내부의 값과 벽을 0개 부순 queue 내부의 값이 있다면

어느 지점이든 벽을 1개 부순 queue 내부의 값이 벽을 0개 부순 queue 내부의 값보다 같거나 빠르게 도착합니다.

 

위의 두 이야기를 종합해서 이해해보면, 큐에 새롭게 삽입하는 조건은 2가지 입니다.

1. 특정 지점에 queue 내부의 값이 최초로 방문한 경우 (벽을 부순 개수 상관 X)

2. 특정 지점에 방문한 queue 내부의 값이 벽을 부순 개수가 이전에 특정 지점에 방문한 queue 내부의 값이 벽을 부순 개수보다 적다면, 이를 갱신하고 큐에 새롭게 삽입합니다. (벽을 부순 개수가 적다면, 경로가 오래걸렸더라도 도착점에 더 빨리 도달할 가능성이 있다)

 

 

정답 코드

#include <sstream>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

ostringstream oss;

struct A {
    int x;
    int y;
    int breakWallCounter;
};

struct B {
    int distance;
    int breakWallCounter;
};

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

int N, M, K;
vector<vector<int> > board;
vector<vector<B> > vis;

void input() {
    cin >> N >> M >> K;
    board.resize(N, vector<int>(M, 0));
    vis.resize(N, vector<B>(M, {0, 0}));

    string inp;
    for (int i = 0; i < N; i++) {
        cin >> inp;
        for (int j = 0; j < M; j++) {
            board[i][j] = inp[j] - '0';
        }
    }

    oss.clear();
    oss.str("");
}

void solution() {
    if (N == 1 && M == 1) {
        oss << 1 << '\n';
        return;
    }
    vis[0][0] = {1, 0};
    queue<A> q;
    q.push({0, 0, 0});

    while (!q.empty()) {
        A cur = q.front();
        q.pop();

        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];

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

            if (nx == N - 1 && ny == M - 1) {
                oss << vis[cur.x][cur.y].distance + 1 << '\n';
                return;
            }


            if (board[nx][ny] == 0) {
                if (vis[nx][ny].distance == 0 || vis[nx][ny].breakWallCounter > cur.breakWallCounter) {
                    vis[nx][ny] = {vis[cur.x][cur.y].distance + 1, cur.breakWallCounter};
                    q.push({nx, ny, cur.breakWallCounter});
                }
            } else {
                if (vis[nx][ny].distance == 0 && cur.breakWallCounter < K || vis[nx][ny].breakWallCounter > cur.breakWallCounter + 1) {
                    vis[nx][ny] = {vis[cur.x][cur.y].distance + 1, cur.breakWallCounter + 1};
                    q.push({nx, ny, cur.breakWallCounter + 1});
                }
            }
        }
    }

    oss << -1 << '\n';
}

void output() {
    cout << oss.str();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    streambuf *pCoutStreamBuf = cout.rdbuf();
    cout.rdbuf(oss.rdbuf());

    input();

    solution();

    cout.rdbuf(pCoutStreamBuf);
    output();
}