(C++) - 백준(BOJ) 16985번 : Maaaaaaaaaze

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

16985번: Maaaaaaaaaze

BFS와 순열구현 문제였습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#define INF 0x7f7f7f7f
using namespace std;
 
int n, m, ans = 0x7f7f7f7f;
 
int dx[6] = { 0,0,-1,1,0,0 };
int dy[6] = { -1,1,0,0,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
 
int d[6][6][6];
int ck[6][6][6];
 
int real_board[6][6][6];
 
int board[6][6][6];
 
int base[5] = { 1,2,3,4,5 };
 
struct xyz {
    //x row
    //y col
    //z floor
    int z, x, y;
};
 
//판쌓기
void pile(int base[]) {
    int cnt = 0;
 
    while (cnt < 5) {
        for (int i = 1; i <= 5; i++) {
            for (int j = 1; j <= 5; j++) {
                board[cnt+1][i][j] = real_board[base[cnt]][i][j];
            }
        }
        cnt++;
    }
}
 
//판 우측회전
void rotate(int which) {
    int tmp[6][6] = { 0 };
 
    //판 임시판에 복사
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            tmp[i][j] = board[which][i][j];
 
    //해당 판을 돌리고 복사.
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            board[which][6 - j][i] = tmp[i][j];
}
 
int bfs(int a, int b, int c) {
    //입구나 출구가 막혔으면 -1반환!
    if (!board[1][1][1] || !board[5][5][5])return INF;
 
    queue <struct xyz> q;
 
    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= 5; j++) {
            for (int k = 1; k <= 5; k++)
                d[i][j][k] = INF;
        }
    }
 
    q.push({ a,b,c });
    d[1][1][1] = 0;
 
    while (!q.empty()) {
 
        int x = q.front().x;
        int y = q.front().y;
        int z = q.front().z;
 
        int tmp = d[z][x][y];
 
        q.pop();
 
        for (int i = 0; i < 6; i++) {
 
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nz = z + dz[i];
 
            if (1 <= nx && nx <= 5 && 1 <= ny && ny <= 5 && 1 <= nz && nz <= 5) {
 
                if (board[nz][nx][ny] == 1 && d[nz][nx][ny] > tmp+1) {
                    d[nz][nx][ny] = tmp+1;
                    q.push({ nz,nx,ny });
                }
            }
        }
    }
    return d[5][5][5];
}
 
void dfs(int cnt) {
 
    if (cnt == 6) { 
        ans = min(ans, bfs(1,1,1));
        return; 
    }
 
    for (int j = 0; j < 4; j++) {
        rotate(cnt);
        dfs(cnt + 1);
    }
 
}
 
int main() {
 
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            for (int k = 1; k <= 5; k++)
                cin >> real_board[i][j][k];
 
    //(1,1,1)에서 시작 (5,5,5)로 탈출
    do {
        //판을 쌓고
        pile(base);
        dfs(1);
 
    } while (next_permutation(base, base + 5));
 
    //탈출 불가능 -1!
    if (ans == INF)
        cout << -1 << '\n';
 
    //출구까지 가는길이 하나라도 있으면 ans들 중 최소 출력
    else
        cout << ans << '\n';
}