[백준 16985번] Maaaaaaaaaze

문제 링크: https://www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

<문제 풀이> 시뮬레이션, BFS, 조합, next_permutation

1. 각 판 회전시키기 구현

 

2. next_permutation을 이용해서 각 판 쌓기 구현

 

3. BFS로 시작점부터 도착점까지 최단거리 구하기

-> 이때 큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다.

-> 시작점을 0, 0, 0 / 도착점을 4, 4, 4로 고정해도 되는 이유는 시작점과 도착점을 고정시키고 판을 잘 회전시키고 잘 쌓으면 다른 꼭짓점에서 출발시킨 것과 동일하다.

 

4. 판을 회전시키는 모든 경우에 대해서 진행

 

<C++ 소스 코드>

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
int maze[5][5][5]; //판을 쌓은 미로
int board[5][5][5]; //5개의 판
int dist[5][5][5];
const int dx[6] = {0, 0, 0, 0, 1, -1};
const int dy[6] = {0, 0, 1, -1, 0, 0};
const int dz[6] = {1, -1, 0, 0, 0, 0};
 
int res = 125;
 
vector<int> v{ 0, 1, 2, 3, 4 }; //쌓일 판의 순서
 
class pos {
public:
    int z;
    int x;
    int y;
    pos(int z, int x, int y) : z(z), x(x), y(y) {
    }
};
 
void stackMaze() {
    for (int z = 0; z < 5; z++) {
        for (int x = 0; x < 5; x++) {
            for (int y = 0; y < 5; y++) {
                maze[z][x][y] = board[v[z]][x][y];
            }
        }
    }
 
}
 
void init() {
    for (int z = 0; z < 5; z++) {
        for (int x = 0; x < 5; x++) {
            for (int y = 0; y < 5; y++) {
                dist[z][x][y] = 0;
            }
        }
    }
}
 
void rotate(int z) {
    int temp[5][5];
    for (int x = 0; x < 5; x++) {
        for (int y = 0; y < 5; y++) {
            temp[x][y] = board[z][x][y];
        }
    }
    for (int x = 0; x < 5; x++) {
        for (int y = 0; y < 5; y++) {
            board[z][y][4 - x] = temp[x][y];
        }
    }
}
 
int bfs() {
    if (maze[0][0][0] == 0 || maze[4][4][4] == 0) return -1; //입구 혹은 출구가 막혀있을 경우
    pos p(0, 0, 0);
    queue<pos> Q;
    Q.push(p);
    dist[p.z][p.x][p.y] = 1;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 6; dir++) {
            int nz = cur.z + dz[dir];
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];
            if (nz < 0 || nx < 0 || ny < 0 || nz >= 5 || nx >= 5 || ny >= 5)continue;
            if (maze[nz][nx][ny] == 0 || dist[nz][nx][ny]) continue;
            Q.push({ nz, nx,ny });
            dist[nz][nx][ny] = dist[cur.z][cur.x][cur.y] + 1;
            if (nz == 4 && nx == 4 && ny == 4) return dist[nz][nx][ny];
        }
    }
    return -1;
}
 
void solve(int k) {
    if (k == 5) return;
    for (int i = 0; i < 4; i++) { //k번째 판을 4번까지 회전시켜본다
        rotate(k); 
        do {
            stackMaze(); 
            int ret = bfs();
            if (ret != -1) res = min(res, ret);
            init();        
        } while (next_permutation(v.begin(), v.end())); //판을 쌓는 순열
        for (int m = 0; m < 5; m++)v[m] = m;
        solve(k + 1); // k+1번째 판을 4번까지 회전시켜본다.
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    for (int z = 0; z < 5; z++) {
        for (int x = 0; x < 5; x++) {
            for (int y = 0; y < 5; y++) {
                cin >> board[z][x][y];
            }
        }
    }
    solve(0);
    if (res == 125) cout << "-1";
    else cout << res - 1;
 
 
    return 0;
}