[BOJ] Maaaaaaaaaze

[문제]

문제

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

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

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

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

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

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

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

입력

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

 

풀이

 

16985

맞았습니다!!

1988

340

C++14 / 수정

4705

12초 전

 

1) 100% 시뮬레이션 문제

 

2) 판이 쌓이는 순서를 조합으로 구했고 next_permutation으로 구현했다. 

넥퍼뮤를 안 쓰고 싶으면 dfs로 해도 될듯.

 

3) 판이 쌓이는 순서를 구하면 c_map에 해당 판의 내용(?)물을 넣어준다. (map은 그대로 보존하고 c_map으로 구현한다.)

 

4) 완성된 c_map을 가지고 판을 회전하고 참가자를 탈출시킬 maze를 만들 playMaze()를 호출한다. 

playMaze()에서는 

• 1번 판부터 시작해서 rotate를 한다. 한 판이 돌아갈 수 있는 방향은 동, 서, 남, 북 4방향이므로 0부터 4까지 반복한다. 
• 1번판이 돌았으면 2,3 ,4,5 도 연쇄적으로 돌아야 하기 때문에 5중 반복문을 해준다. 
• 5번판까지 다 돌았을 때 "큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다." 를 만족하는 1번 칸의 (1,1) 좌표와 5번 칸의 (5,5)가 1(참가자가 입장할 수 있는 공간) 이면 이제 미로를 빠져나간다. (bfs)

4-1) 판을 회전시키는 rotate함수에서는 회전을 할 때 좌표들을 그려가면서 저장을 해주면 된다. 

1,1	1,2	1,3	1,4	1,5
				2,5
				3,5
				4,5
				5,5

 

시계방향 90도 회전한 결과 

 

5,1	4,1	3,1	2,1	1,1
			2,2	1,2
			2,3	1,3
			2,4	1,4
			2,5	1,5

 

이렇게 그려나가다보면 어느 정도 규칙성이 보인다. 

 

[1,1] -> [5,1]

[1,2] -> [4,1]

[1,3] -> [3,1]

[1,4] -> [2,1]

[1,5] -> [1,1]

 

---> 회전 후의 y좌표가 1부터 증가하면 회전 전의 x좌표는 5부터 감소한다. 

 

회전 후의 결과는 다시 c_map에 넣어준다. 

 

5) bfs에서는 그냥 완탐한다. 

여기서 다른 점은 x,y 좌표 뿐 아니라 z(높이)도 봐야하기 때문에 평소처럼 4번 반복이 아니라 [위, 아래]도 포함해서 6번 돌려준다. 

만약, [5,5,5,]에 도달하면 그때의 이동 횟수를 반환한다. 

 

---

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
 
#define INF 987654321
using namespace std;
 
int map[6][6][6], c_map[6][6][6], ans = INF;
int dx[6] = {-1, 1, 0, 0, 0, 0}, dy[6] = {0, 0, -1, 1, 0, 0}, dz[6] = {0, 0, 0, 0, -1, 1};
typedef pair<int, int> pp;
typedef pair<pp, pp> pppp;
 
void rotate(int idx)
{
    //시계방향 혹은 반시계방향으로 회전
    int tmp_map[6][6] = {{0}};
    //회전한 결과 저장
    //회전 하기 전의 y는 회전 후의 x가 되고, 회전 하기 전의 x는 회전 후의 5-x+1 이 된다.
    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= 5; j++)
        {
            tmp_map[i][j] = c_map[idx][j][5 - i + 1];
        }
    }
    memcpy(c_map[idx], tmp_map, sizeof(tmp_map));
}
int bfs()
{
    //미로 탈출
 
    //1,1,1 -> 5.5.5
    queue<pppp> q;
    q.push(pppp(pp(0, 1), pp(1, 1)));
 
    bool visited[6][6][6] = {{{0}}};
 
    visited[1][1][1] = true;
    int res = INF;
    while (!q.empty())
    {
        int size = q.size();
        while (size--)
        {
            int x = q.front().second.first;
            int y = q.front().second.second;
            int z = q.front().first.second;
            int cnt = q.front().first.first;
 
            q.pop();
 
            if (z == 5 && x == 5 && y == 5)
            {
                ans = min(ans, cnt);
                continue;
            }
 
            //밑으로 내려가는 방향으로 향해야 하기 때문에 북쪽 방향은 하지 안흔ㄴ다?
 
            for (int i = 0; i < 6; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int nz = z + dz[i];
 
                if (nx <= 0 || nx > 5 || ny <= 0 || ny > 5 || nz <= 0 || nz > 5 || visited[nx][ny][nz] || !c_map[nx][ny][nz])
                    continue;
 
                visited[nx][ny][nz] = true;
                q.push(pppp(pp(cnt + 1, nz), pp(nx, ny)));
            }
        }
    }
    return res;
}
void playMaze()
{
    //처음 시작할 지점은 임의의 점
    //도착지점은 시작 지점과 면이 닿지 않는 지점 1번 칸의 (1,1) 5번 칸의 (5,5)
    //1은 참가자가 들어갈 수 있는 칸
    if (c_map[1][1][1] && c_map[5][5][5])
    {
        int res = bfs();
        ans = min(ans, res);
    }
 
    //연쇄 회전
    for (int i = 0; i < 4; i++)
    {
        rotate(1);
        for (int j = 0; j < 4; j++)
        {
            rotate(2);
            for (int k = 0; k < 4; k++)
            {
                rotate(3);
                for (int z = 0; z < 4; z++)
                {
                    rotate(4);
                    for (int a = 0; a < 4; a++)
                    {
                        rotate(5);
                        if (c_map[1][1][1] && c_map[5][5][5])
                        {
                            int res = bfs();
                            ans = min(ans, res);
                        }
                    }
                }
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    vector<int> v;
    for (int k = 1; k <= 5; k++)
    {
        v.push_back(k);
        for (int i = 1; i <= 5; i++)
        {
            for (int j = 1; j <= 5; j++)
            {
                cin >> map[k][i][j];
            }
        }
    }
 
    do
    {
        // 판의 순서를 순열로 정한다.
        for (int k = 0; k < 5; k++)
        {
            memcpy(c_map[k + 1], map[v[k]], sizeof(map[v[k]]));
 
        }
 
        playMaze();
    } while (next_permutation(v.begin(), v.end()));
 
    if (ans == INF)
        cout << -1 << '\n';
    else
        cout << ans << '\n';
 
    return 0;
}