백준 16933번: 벽 부수고 이동하기 3 (C++)

접근

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

16933번: 벽 부수고 이동하기 3

bfs 알고리즘을 이용하는 문제였다.

문제를 해결하기 위해 큐에 4가지 정보를 저장하였다. {r, c, night: 밤이면 1, cnt: 부순 벽의 갯수} 총 4개의 요소를 가진 구조체를 작성해주고, 이를 저장할 수 있는 큐에 가장 처음 위치인 {0, 0, 0, 0} 을 추가해주었다.

중복 탐색을 막기 위한 배열인 visited 배열은 visited[N][M][K][2] 로 N * M * K 에 낮과 밤을 표시하기 위해 * 2 크기로 선언하고, 최댓값을 갖도록 INF로 초기화해주었다. 이 배열의 각 칸에는 (N, M) 위치에서 벽 부순 횟수가 K이며 낮/밤일 때의 최소 이동 거리를 저장해준다. 따라서, 탐색이 완료된 후에는 visited[N][M]에서 (K + 1) * 2 개의 숫자 중 최솟값이 정답이 된다.

탐색 과정에서 {r, c, night, cnt} 칸을 탐색하고 있을 때, 이 위치에서 이동할 수 있는 방법은 총 5가지이다. 상하좌우 4방향과 가만히 있는 방법.

1. 상하좌우 4방향으로 이동하기 위해서는 해당 방향에 벽이 있을 때와 벽이 없을 때로 나눌 수 있다. 벽이 없을 때에는 다음 위치에 저장된 이동 거리가 현재 위치 이동거리 + 1 보다 클 경우에만 이동할 수 있다. 이 경우 {nr, nc, 1 - night, cnt} 를 큐에 추가해준다. 벽이 있을 때에는 벽이 없을 때의 조건 + 현재가 낮일 경우(night = 0), 부순 횟수가 충분할 경우(cnt < K)에 이동할 수 있다. 이 경우 {nr, nc, 1 - night, cnt + 1} 을 큐에 추가해준다.
2. 현재 위치에 가만히 있는 경우 {r, c, 1 - night, cnt} 를 큐에 추가해준다.

조건에 맞추어 탐색이 완료되면 정답을 구할 수 있다.

코드

#include <iostream>
#include <queue>
#include <string>

using namespace std;

#define endl '\n'
#define MAX_N 1001
#define MAX_K 11
#define INF 10000000

struct INFO {
    int r;
    int c;
    int night;
    int cnt;
};

int N, M, K;
char MAP[MAX_N][MAX_N];
int visited[MAX_N][MAX_N][MAX_K][2];

int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};

int MinVal(int a, int b) {
    if (a <= b) {
        return a;
    } else {
        return b;
    }
}

bool OutMap(int r, int c) {
    return (r < 0 || N <= r || c < 0 || M <= c);
}

int bfs() {
    // visited 배열을 INF로 초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int k = 0; k <= K; k++) {
                visited[i][j][k][0] = INF;
                visited[i][j][k][1] = INF;
            }
        }
    }
    queue<INFO> Q;
    // {r, c, night, cnt} 정보 추가
    Q.push({0, 0, 0, 0});
    visited[0][0][0][0] = 1;
    while (!Q.empty()) {
        int r = Q.front().r;
        int c = Q.front().c;
        int night = Q.front().night;
        int cnt = Q.front().cnt;
        Q.pop();
        // 상하좌우 4방향으로 이동할 때
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (OutMap(nr, nc)) continue;
            if (MAP[nr][nc] == '0' && visited[r][c][cnt][night] + 1 < visited[nr][nc][cnt][1 - night]) {
                // 벽이 없을 경우, 다음 위치의 visited 값이 현재 위치 값 + 1 보다 클 경우 이동 가능
                visited[nr][nc][cnt][1 - night] = visited[r][c][cnt][night] + 1;
                Q.push({nr, nc, 1 - night, cnt});
            } else if (MAP[nr][nc] == '1' && night == 0 && cnt < K && visited[r][c][cnt][night] + 1 < visited[nr][nc][cnt + 1][1 - night]) {
                // 벽이 있을 경우, 다음 위치의 visited 값이 현재 위치 값 + 1 보다 크고, 낮인 상태이고, 벽을 부순 횟수가 충분할 경우 이동 가능
                visited[nr][nc][cnt + 1][1 - night] = visited[r][c][cnt][night] + 1;
                Q.push({nr, nc, 1 - night, cnt + 1});
            }
        }
        // 현재 위치에 가만히 있을 경우
        if (visited[r][c][cnt][night] + 1 < visited[r][c][cnt][1 - night]) {
            visited[r][c][cnt][1 - night] = visited[r][c][cnt][night] + 1;
            Q.push({r, c, 1 - night, cnt});
        }
    }
    // (N - 1, M - 1) 에 도달할 수 있는 모든 경우 비교
    int ans = INF;
    for (int i = 0; i <= K; i++) {
        for (int j = 0; j < 2; j++) {
            ans = MinVal(ans, visited[N - 1][M - 1][i][j]);
        }
    }
    if (ans == INF) {
        return -1;
    } else {
        return ans;
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> MAP[i][j];
        }
    }
    cout << bfs() << endl;

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!