백준 16954번: 움직이는 미로 탈출

접근

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

16954번: 움직이는 미로 탈출

체스판의 크기가 8이므로, 벽이 총 8회 움직이고 나면 체스판에 벽이 사라지게 된다. 즉, 욱제가 8턴까지 벽에 맞지 않고 살아있다면 체스판을 탈출할 수 있다고 생각하고 dfs 알고리즘을 이용하여 풀이하였다.

추가적으로 벽의 좌표를 구조체로 만들어 총 8개의 배열에 저장(벽이 총 7번 이동할 때까지 욱제가 살아있으면 체스판 탈출 가능)해주었고, 욱제가 이동할때 해당하는 벽의 위치에 있는지 아닌지를 확인하면서 탐색해주었다. dfs 깊이를 이동 횟수라고 생각하고 탐색하면서 이 depth가 8 이상이 되면 ans를 1로 바꿔주고 탐색을 종료하였다.

코드

#include <iostream>

using namespace std;

#define endl '\n'

struct BLOCK {
    int r;
    int c;
};

char MAP[9][9];
int n_block = 0, ans = 0;

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

// Block의 위치를 저장하는 배열, Block[a][b]: a번 이동했을 때 b번 블록의 위치
BLOCK Block[8][65];

bool MapOut(int r, int c) {
    return (r < 0 || 8 <= r || c < 0 || 8 <= c);
}

// (r, c)의 위치와 depth번 이동한 벽의 위치를 비교하여 벽의 위치에 있는지 아닌지를 판단
bool blocked(int r, int c, int depth) {
    for (int i = 0; i < n_block; i++) {
        if (r == Block[depth][i].r && c == Block[depth][i].c) {
            return true;
        }
    }
    return false;
}

void dfs(int r, int c, int depth) {
    if (8 < depth) {
        // 8번 이동하고도 욱제가 살아있다면 체스판 탈출 가능
        ans = 1;
        return;
    }
    if (ans == 1) return;
    // 벽에 맞으면 return
    if (blocked(r, c, depth)) return;
    for (int i = 0; i < 9; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (MapOut(nr, nc)) continue;
        // 다음 위치에 벽이 있다면 continue
        if (blocked(nr, nc, depth)) continue;
        dfs(nr, nc, depth + 1);
    }
}

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

    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cin >> MAP[i][j];
            if (MAP[i][j] == '#') {
                Block[0][n_block++] = {i, j};
            }
        }
    }
    for (int i = 0; i < n_block; i++) {
        for (int j = 1; j < 8; j++) {
            int nr = Block[0][i].r + j;
            int nc = Block[0][i].c;
            if (MapOut(nr, nc)) {
                nr = -1;
                nc = -1;
            }
            Block[j][i] = {nr, nc};
        }
    }
    dfs(7, 0, 0);

    cout << ans << endl;

    return 0;
}

더 생각해 볼 것?

...

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