[백준 - 16985] Maaaaaaaaaze - C++

분류: 3차원 BFS, 시뮬레이션 /

 

문제

문제 링크

문제 설명

평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다.

대회의 규칙은 아래와 같다.

• 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸을, 검은 칸은 참가자가 들어갈 수 없는 칸을 의미한다.

• 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있다. 그러나 판을 뒤집을 수는 없다.

• 회전을 완료한 후 참가자는 판 5개를 쌓는다. 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다. 이렇게 판 5개를 쌓아 만들어진 5×5×5 크기의 큐브가 바로 참가자를 위한 미로이다. 이 때 큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다.

• 참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있다.
• 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승한다. 만약 미로의 입구 혹은 출구가 막혀있거나, 입구에서 출구에 도달할 수 있는 방법이 존재하지 않을 경우에는 탈출이 불가능한 것으로 간주한다.

이 대회에서 우승하기 위해서는 미로를 잘 빠져나올 수 있기 위한 담력 증진과 체력 훈련, 그리고 적절한 운이 제일 중요하지만, 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만드는 능력 또한 없어서는 안 된다. 주어진 판에서 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만들었을 때 몇 번 이동을 해야하는지 구해보자.

입력

첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다.

출력

첫째 줄에 주어진 판으로 설계된 미로를 탈출하는 가장 적은 이동 횟수를 출력한다. 단, 어떻게 설계하더라도 탈출이 불가능할 경우에는 -1을 출력한다.

 

풀이

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX_DIST = 125;

struct lxy {int l, x, y;};
bool maze[5][5][5];
int dl[] = {1, -1, 0, 0, 0, 0};
int dx[] = {0, 0, 1, -1, 0, 0};
int dy[] = {0, 0, 0, 0, 1, -1};
int level[5] = {0, 1, 2, 3, 4};

bool OOB(int l, int x, int y) {
    return l<0 || l>4 || x<0 || x>4 || y<0 || y>4;
}
void rotate90(int stage) {
    int tmp[5][5];
    for(int x=0; x<5; x++)
        for(int y=0; y<5; y++)
            tmp[x][y] = maze[stage][x][y];
    for(int x=0; x<5; x++)
        for(int y=0; y<5; y++)
            maze[stage][y][4-x] = tmp[x][y];
}
int bfs() {
    if(!(maze[level[0]][0][0] && maze[level[4]][4][4]))
        return MAX_DIST;
    bool vis[5][5][5] = {};
    vis[0][0][0] = true;
    queue<lxy> Q;
    Q.push({0, 0, 0});
    int dist = 0;
    while(!(Q.empty() || vis[4][4][4])) {
        dist++;
        for(int size = Q.size(); size--;) {
            lxy cur = Q.front(); Q.pop();
            for(int dir=6; dir--;) {
                int nl = cur.l + dl[dir];
                int nx = cur.x + dx[dir];
                int ny = cur.y + dy[dir];
                if(OOB(nl, nx, ny)) continue;
                if(vis[nl][nx][ny]) continue;
                if(!maze[level[nl]][nx][ny]) continue;
                vis[nl][nx][ny] = true;
                Q.push({nl, nx, ny});
            }
        }
    }
    return vis[4][4][4] ? dist : MAX_DIST;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    for(int i=0; i<5; i++)
        for(int j=0; j<5; j++)
            for(int k=0; k<5; k++)
                cin >> maze[i][j][k];
    
    int ans = MAX_DIST;
    for(int rot = 0; rot < 1024; rot++) {
        int dirs[5];
        int tmp = rot;
        for(int stage = 0; stage < 5; stage++) {
            dirs[stage] = tmp & 3;
            tmp >>= 2;
        }
        for(int stage = 0; stage < 5; stage++)
            for(int i=0; i < dirs[stage]; i++)
                rotate90(stage);
        
        do {
            ans = min(ans, bfs());
        } while(next_permutation(level, level+5));

        for(int stage = 0; stage < 5; stage++)
            for(int i=0; dirs[stage] && i < 4-dirs[stage]; i++)
                rotate90(stage);
    }
    cout << (ans == MAX_DIST ? -1 : ans);
}

 5개의 판과 층을 따로 생각해야한다.

5 by 5 판 5개(`maze[stage][x][y]`)가 있고 `stage`를 층으로 쌓은 순서를 의미하는 `level[5]`를 든다.

`level[0] == 2`의 의미는 0번째 층이 `maze[2][x][y]`라는 뜻이다.

따라서 `(층, x, y)`를 나타내는 3차원 좌표 `(l, x, y)`는 `maze[level[l][x][y]`를 의미한다.

1. 5개의 판을 0, 90, 180, 270도로 회전하는 모든 경우의 수(4⁵=1024)에 대해 판을 회전한다.
2. 각 회전된 판으로 층으로 쌓는다. `5! = 120`, (`next_permutation(level, level+5)`)
3. 만들어진 3차원 미로에 대해 3차원 BFS를 실행한다.

시간복잡도는 4⁵ * 5! * 5³ = 15,360,000

 

각 판을 회전시키는 모든 경우의 수를 비트를 이용해 구현한 것은 [백준 - 15683] 감시문제에서 알게된 방법으로 서로 독립적인 상태를 완전탐색할 때 아주 유용하다.

 

모든 판의 회전이 완료되면 층을 모든경우(5!)로 쌓고 쌓인 층에대해 BFS를 수행한다.

`maze`를 `maze[level[l]][x][y]`로 사용해야함에 중의하자. `vis`는 `vis[l][x][y]`로 사용해도 된다.

 

2차원 판의 회전은 [백준 - 12100] 2048 (Easy)와 같은 문제들에서 많이 다뤘었다.