백준 16985 - Maaaaaaaaaze(C++)

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

16985번: Maaaaaaaaaze

BFS와 구현, 브루트포스가 합쳐진 문제였습니다.

문제 자체는 간단하지만 구현 능력이 있어야했던 문제입니다.

 

5개 층의 Map이 주어지고, 이를 통해 미로를 구성한 뒤 탈출할 수 있는지를 확인하는 문제입니다.

 

이 문제를 풀기 위해서 구현해야할 것이 있습니다.

1. 5개 층을 선택하기

2. 층을 반시계 혹은 시계 방향으로 돌리기

3. 구성된 미로를 탐색하기

 

먼저 5개 층을 선택하는 방법입니다.

주어진 1~5층을 선택해서 각 층에 넣어주면 됩니다.

나올 수 있는 경우는 (1,2,3,4,5), (1,2,3,5,4), (1,2,4,3,5) .... (5,4,3,2,1) 입니다.

따라서 백트래킹 방법을 이용해 5개 층을 선택해주면 됩니다.

 

2번째는 미로를 움직이는 방법입니다.

미로의 한 층을 돌릴때, 나오는 경우는 4가지입니다.(시계 혹은 반시계의 경우입니다.)

따라서 시계 혹은 반시계 방향으로 돌리는 방법을 하나 선택한 뒤에 해당 방법을 4번 반복해주시면 됩니다.

 

돌려지는 층이 5개이니 어떤 층부터 돌려야하는지 순서를 정해야합니다.

저의 경우 맨 아랫층부터 돌리기 시작해 맨 윗층으로 마무리 했습니다.

따라서 for문을 5개를 이용해 윗층 혹은 아랫층부터 순서대로 돌려주시면 됩니다.

 

저의 경우는 층을 돌리는 방법을 반시계 방향으로 정했습니다.

예시를 들어 반시계 방향으로 돌렸을 때 좌표가 어떻게 변하는지 확인하겠습니다.

11111                                12345

22222                               12345

33333              ->              12345

44444                               12345

55555                               12345

(0, 0) -> (4, 0)

(1, 4) -> (0, 1)

(2, 2) -> (2, 2)

(3, 3) -> (1, 3)

(4, 1) -> (3, 4)

해당 좌표로 이동한 것을 볼 수 있습니다.

이를 통해서 확인할 수 있는 것은 (X, Y) -> (4-Y, X) 로 바뀐 것을 볼 수 있습니다.

위의 식으로 좌표를 옮기면 됩니다.

 

층을 구성하고 돌린 미로를 매 경우마다 BFS로 탐색하면 됩니다.

이때 3차원이기에 위, 아래를 포함한 6방향 탐색을 해주시면 됩니다.

 

시작점에 들어갈 수 없는 경우, 도착점에 도착할 수 없는 경우에는 -1를, 아닌 경우에는 탐색 횟수를 return해서 가장 작은 탐색 횟수를 계속 확인했습니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>
#define P pair<int, int>
#define PP pair<P, P>
#define F first
#define S second
#define INF 1000000000

using namespace std;

int Maze[5][5][5]; // layer, x, y
int layer[5][5][5];
int check[5][5][5];
int Check[5];
vector<int> Select;
int dx[6] = {1,0,-1,0,0,0};
int dy[6] = {0,1,0,-1,0,0};
int dz[6] = {0,0,0,0,-1,1};
int ans = INF;

void turn_maze(int x){ // x->layer
    int after[5][5];
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            after[i][j] = Maze[x][4-j][i];
        }
    }
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            Maze[x][i][j] = after[i][j];
        }
    }
}

int bfs(){
    if(Maze[0][0][0] == 0) return -1;
    if(Maze[4][4][4] == 0) return -1;
    memset(check, 0, sizeof(check));
    queue<PP> q;
    q.push({{0,0}, {0,0}}); // x,y,layer,cnt
    check[0][0][0] = 0;
    while(!q.empty()){
        int x = q.front().F.F;
        int y = q.front().F.S;
        int z = q.front().S.F;
        int cnt = q.front().S.S;
        q.pop();
        if(x == 4 && y == 4 && z == 4) return cnt;
        for(int i = 0; i < 6; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            int zz = z + dz[i];
            if(xx >= 0 && xx <= 4 && yy >= 0 && yy <= 4 && zz >= 0 && zz <= 4){
                if(check[zz][xx][yy] == 0 && Maze[zz][xx][yy] == 1){
                    check[zz][xx][yy] = 1;
                    q.push({{xx,yy},{zz,cnt+1}});
                }
            }
        }
    }
    return -1;
}

void move_in_miro(){
    for(int v = 0; v < 4; v++){
        for(int w = 0; w < 4; w++){
            for(int x = 0; x < 4; x++){
                for(int y = 0; y < 4; y++){
                    for(int z = 0; z < 4; z++){
                        turn_maze(4);
                        int cnt = bfs();
                        if(cnt != -1) ans = min(ans, cnt);
                    }
                    turn_maze(3);
                }
                turn_maze(2);
            }
            turn_maze(1);
        }
        turn_maze(0);
    }
}

void select_layer(int start, int now, int cnt){
    if(now == cnt){
        for(int k = 0; k < 5; k++){
            for(int i = 0; i < 5; i++){
                for(int j = 0; j < 5; j++){
                    Maze[k][i][j] = layer[Select[k]][i][j];
                }
            }
        }
        move_in_miro();
    }
    else{
        for(int i = 0; i < 5; i++){
            if(i == start) continue;
            if(Check[i] == 0){
                Check[i] = 1;
                Select.push_back(i);
                select_layer(i, now+1, cnt);
                Select.pop_back();
                Check[i] = 0;
            }
        }
    }
}

void solve(){
    for(int i = 0; i < 5; i++){
        Check[i] = 1;
        Select.push_back(i);
        select_layer(i, 1, 5);
        Select.pop_back();
        Check[i] = 0;
    }
    if(ans == INF) cout << "-1";
    else cout << ans;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    for(int k = 0; k < 5; k++){
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                cin >> layer[k][i][j];
            }
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요!