백준 g2 16985 Maaaaaaaaaze c++

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

16985번: Maaaaaaaaaze

 

문제 설명

• 5*5 판이 5개 주어지고, 참가자가 들어갈 수 있는 칸과 그렇지 않은 칸이 각각 1, 0 으로 주어진다.
• 5개의 판을 순서 상관 없이 자유롭게 쌓을 수 있고, 각각 자유롭게 회전이 가능하다. (뒤집는 건 X)
• 맨 위 임의의 꼭짓점을 입구로 정하면, 그 반대쪽 아래에 있는 꼭짓점이 출구가 된다.
• 이렇게 완성된 5*5*5 미로를 탈출하는 최소거리를 구하는 것이 목표
• 만약 입구 혹은 출구가 막혀있거나, 출구에 도달할 수 없을 때는 탈출이 불가능한 것으로 간주한다

풀이

 

전체 흐름

1. 5개의 판을 섞는 경우의 수 5!

2. 가능한 입구 4개 중 하나 선택 4 //동시에 출구도 정해짐

3. 맨 윗 판(0층)을 제외하고, 1~4층을 어떻게 돌릴 건지 중복순열 4*4*4*4 = 2^8

4. 5*5*5 미로가 완성되었으므로, 입구 -> 출구까지 BFS 125

 

1. 5개의 판을 섞는 경우의 수 5!

order 배열을 두고, next_permutation으로 모든 경우의 수를 구함

int order[5] = {0, 1, 2, 3, 4}; // 판 쌓는 순서, order[i]: i층에 몇 번 판이 놓일 건지
do {
        ...
    }
} while (next_permutation(order, order + 5));

 

2. 가능한 입구 4개 중 하나 선택 4

 

가능한 시작점을 startX와 startY로 지정해놓고, for(s: 4)로 모든 경우의 수 탐색

이때, 고른 입구가 막혀있는 칸이면 (board==0) continue

int startX[4] = {0, 0, 4, 4};
int startY[4] = {0, 4, 0, 4};


// 2. 첫번째 판의 시작점 정하기
for (int s = 0; s < 4; s++) {
    initialize();
    fx = startX[s];
    fy = startY[s];
    // 2-1. if 시작점이 막혀있으면 continue)
    if (board[fx][fy][order[0]] == 0) continue;

	
    // 3. 밑 4개의 판을 돌리기 & 돌려진 판으로 bfs 돌리기
    // 첫 판은 무조건 rot == 0
    rot[order[0]] = 0;
    dfs(1);
}

 

3. 맨 윗 판(0층)을 제외하고, 1~4층을 어떻게 돌릴 건지 중복순열 4*4*4*4 = 2^8

 

rot[5]가 다 채워지면 == 1~4층을 어떻게 돌릴 건지 정해지면, 정해진 rot를 바탕으로 bfs를 수행한다.

그 전에, 어떻게 회전할지가 다 정해졌기 때문에 출구의 좌표도 계산할 수 있다.

 

bfs를 돌리기 전에 출구 좌표를 계산해서 만약 출구가 막혀있다면 그대로 return 해준다.

어떻게 좌표를 돌리는지는 밑에서 설명하겠음

 

int rot[5]; //rot: 몇 번 판을 얼마나 돌릴 건지, 몇 층을 얼마나 돌릴 건지가 아님에 유의

//맨 윗 판은 회전 안해도 됨, 0 고정
rot[order[0]] = 0;
dfs(1);

void dfs(int k) { // rot[k]를 정해야 함, k번 판을 얼마나 돌릴 건지
    if (k == 5) {
        initialize();
        // 3. 돌려진 판으로 bfs 시작
        // 3-1. 도착점이 막혀있으면 continue
        ex = fx == 4 ? 0 : 4;
        ey = fy == 4 ? 0 : 4;
        int temp;
        tie(ex, ey, temp) = rotZ(ex, ey, order[4], order[0]); //맨 밑 층(4층) 돌려서 좌표 확인
        if (board[ex][ey][order[4]] == 0) return;

        int res = bfs();
        mx = min(mx, res);
        return;
    }

    for (int i = 0; i < 4; i++) {
        rot[order[k]] = i;
        dfs(k + 1);
    }
}

 

3-1. 판을 돌리는 방법

 

돌리는 방법은 판 자체를 돌리지 않고, 돌려진 좌표를 역으로 계산해 원래 그 판에서의 좌표를 계산하는 방식을 썼다.

원래 좌표가 (0, 0, 0)이고 밑 층이 시계 방향으로 90도 돌아가 있는 경우를 생각해보자

(0, 0, 0)에서 바로 아래 층으로 이동할 때, 아래 층이 시계 방향으로 90도 돌아가 있지 않다면 (0, 0, 1)에 안착했을 것이다.

그러나 밑 층이 90도로 돌아가 있는 상태이기 때문에 원래 좌표에서 시계 반대 방향으로 90도를 돌려야 그 층에서의 좌표가 나온다.

 

그림에서도 아래층에서의 좌표는 (4, 0, 1)이 되고, 이는 원래 좌표에서 시계 반대 방향으로 90도를 돌린 것과 같다.

 

여기서 rot 값은 각각 다음과 같다.

 

0: 원본, 1: CW 90도, 2: CW 180도, 3: CW 270도

x, y: 바뀌기 전 윗 층에서의 좌표
nz: 밑 층의 판 번호(board에서 몇 번째 판인지)

z: 윗 층의 판 번호

tuple<int, int, int> rotZ(int x, int y, int nz, int z) {
    //x, y: 바뀌기 전 윗 층에서의 좌표
    //nz: 밑 층의 판 번호(board에서 몇 번째 판인지), z: 윗 층의 판 번호
    
    int rotDiff = rot[nz] - rot[z]; // 현재 z판과 nz판의 각도 차이
    // 현재 z에 비해 이동할 판이 돌아간 상태니까, 반대로 돌린다
    
    /* rotDiff 값
        3 -> -270 = 90도
        2 -> -180 = 180도
        1 -> -90 = 270도
        0 -> 그대로
        -1 -> 90도
        -2 -> 180도
        -3 -> 270도
    */
    if (rotDiff == 0)
        return make_tuple(x, y, nz);
    else if (rotDiff == 3 || rotDiff == -1) { // CW 90도
        return make_tuple(y, 4 - x, nz);
    } else if (rotDiff == 2 || rotDiff == -2) { // CW 180도
        return make_tuple(4 - x, 4 - y, nz);
    } else if (rotDiff == 1 || rotDiff == -3) { // CW 270
        return make_tuple(4 - y, x, nz);
    }
    else {
        cout << "error\n"
             << "\n";
        exit(1);
    }
}

 

4. 5*5*5 미로가 완성되었으므로, 입구 -> 출구까지 BFS 125

 

다음 층수를 계산하려면 판 번호가 아니라 몇 층인지 정보가 필요하므로, Q에 기록해두었다. 

getNext() 함수는 rotZ()함수를 출구 구할 때 써야하기 때문에 따로 빼둔 용도

인데 지금 보니 따로 안 빼도 될 것 같다

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

tuple<int, int, int> getNext(int nx, int ny, int nz, int z, int dir) {
    // 위, 아래가 아닌 상하좌우로만 이동
    if (z == nz) return make_tuple(nx, ny, nz);

    return rotZ(nx, ny, nz, z);
}

int bfs() {
    queue<tuple<int, int, int, int>> Q; // x, y, z, 층수
    vis[fx][fy][order[0]] = 1;
    Q.push({fx, fy, order[0], 0});

    while (!Q.empty()) {
        int x, y, z, floor;
        tie(x, y, z, floor) = Q.front();
        Q.pop();

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

            int nf = floor + dz[dir]; // 층수 +1 -1로 계산

            if (nf < 0 || nf >= 5) continue;
            int nz = order[nf]; // 실제 판 번호, 몇 번째 판인지 board에서 z값 구하기

            if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            // if (nz < 0 || nz >= 5) continue;

            tie(nx, ny, nz) = getNext(nx, ny, nz, z, dir);

            if (board[nx][ny][nz] == 0) continue;
            if (vis[nx][ny][nz] > 0) continue;

            vis[nx][ny][nz] = vis[x][y][z] + 1;
            Q.push({nx, ny, nz, nf});
        }
    }

    if (vis[ex][ey][order[4]] == 0)
        return MX;
    else {
        return vis[ex][ey][order[4]];
    }
}

 

 

전체 코드

/*boj g2 16985 Maaaaaaaaaze*/
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#define MAXN 6
#define MX 9999
using namespace std;

int board[MAXN][MAXN][MAXN]; // x, y, z z가 층
int vis[MAXN][MAXN][MAXN];

int startX[4] = {0, 0, 4, 4};
int startY[4] = {0, 4, 0, 4};
int order[5] = {0, 1, 2, 3, 4}; // 판 쌓는 순서

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

int fx, fy, ex, ey;

int rot[5];
int mx = MX;

void input() {
    for (int k = 0; k < 5; k++) {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                cin >> board[i][j][k];
            }
        }
    }
}

void initialize() {
    for (int k = 0; k < 5; k++) {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                vis[i][j][k] = 0;
            }
        }
    }
}

tuple<int, int, int> rotZ(int x, int y, int nz, int z) {
    int rotDiff = rot[nz] - rot[z]; // 현재 z판과 nz판의 차이
    // 현재 z에 비해 이동할 판이 돌아간 상태니까, 반대로 돌린다

    if (rotDiff == 0)
        return make_tuple(x, y, nz);
    else if (rotDiff == 3 || rotDiff == -1) { // CW 90도
        return make_tuple(y, 4 - x, nz);
    } else if (rotDiff == 2 || rotDiff == -2) { // CW 180도
        return make_tuple(4 - x, 4 - y, nz);
    } else if (rotDiff == 1 || rotDiff == -3) { // CW 270
        return make_tuple(4 - y, x, nz);
    }
    /*
        3 -> -270 = 90도
        2 -> -180 = 180도
        1 -> -90 = 270도
        0 -> 그대로
        -1 -> 90도
        -2 -> 180도
        -3 -> 270도
    */
    else {
        cout << "error\n"
             << "\n";
        exit(1);
    }
}

tuple<int, int, int> getNext(int nx, int ny, int nz, int z, int dir) {
    // 위, 아래가 아닌 상하좌우로만 이동
    if (z == nz) return make_tuple(nx, ny, nz);

    return rotZ(nx, ny, nz, z);
}

int bfs() {
    queue<tuple<int, int, int, int>> Q; // x, y, z, 층수
    vis[fx][fy][order[0]] = 1;
    Q.push({fx, fy, order[0], 0});

    while (!Q.empty()) {
        int x, y, z, floor;
        tie(x, y, z, floor) = Q.front();
        Q.pop();

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

            int nf = floor + dz[dir]; // x, y, z, 층수

            if (nf < 0 || nf >= 5) continue;
            int nz = order[nf];

            if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            // if (nz < 0 || nz >= 5) continue;

            tie(nx, ny, nz) = getNext(nx, ny, nz, z, dir);

            if (board[nx][ny][nz] == 0) continue;
            if (vis[nx][ny][nz] > 0) continue;

            vis[nx][ny][nz] = vis[x][y][z] + 1;
            Q.push({nx, ny, nz, nf});
        }
    }

    if (vis[ex][ey][order[4]] == 0)
        return MX;
    else {
        return vis[ex][ey][order[4]];
    }
}

void dfs(int k) { // rot[k]를 정해야 함, k번째 판을 얼마나 돌릴 건지
    if (k == 5) {
        initialize();
        // 3. 돌려진 판으로 bfs 시작
        // 3-1. 도착점이 막혀있으면 continue
        ex = fx == 4 ? 0 : 4;
        ey = fy == 4 ? 0 : 4;
        int temp;
        tie(ex, ey, temp) = rotZ(ex, ey, order[4], order[0]);
        if (board[ex][ey][order[4]] == 0) return;

        int res = bfs();
        mx = min(mx, res);
        return;
    }

    for (int i = 0; i < 4; i++) {
        rot[order[k]] = i;
        dfs(k + 1);
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    // 1. 판 쌓는 순서 next_permutation
    do {
        // 2. 첫번째 판의 시작점 정하기
        for (int s = 0; s < 4; s++) {
            initialize();
            fx = startX[s];
            fy = startY[s];
            // 2-1. if 시작점이 막혀있으면 continue)
            if (board[fx][fy][order[0]] == 0) continue;

            // 3. 밑 4개의 판을 돌리기 & 돌려진 판으로 bfs 돌리기
            // 첫 판은 무조건 rot == 0
            rot[order[0]] = 0;
            dfs(1);
        }
    } while (next_permutation(order, order + 5));

    if (mx == MX)
        mx = -1;
    else
        mx--;
    cout << mx << "\n";
}

 

실수했던 점

 

1. vis 초기화는 bfs 전에 반드시, dfs함수 안에 넣어야 함

2. board[i][j][k]에서 k가 층이므로, board[k][i][j] 순서가 맞음

 

 

사담

이외에도 수많은 실수 .. 애초에 문제를 잘 못 읽어서 5개 판 순서를 자유롭게 해도 되는지를 빼먹었다

시뮬레이션을 너무 오랜만에 풀었나보다

시뮬레이션은 항상 중요한 게

1. 문제 꼼꼼히 읽기 -> 이것만 해도 오류 잡는 경우 많음

2. 정신 차리고 코드 짜기 -> 코드가 복잡하기 때문에 처음 코드 작성할 때 실수하면 잡기 힘듦 ..