[ 백준 16985 ] Maaaaaaaaaze (C++)

백준의 Maaaaaaaaaze(16985) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 문제가 상당히 골 때린다. 쓰읍...  문제 푸는 큰 순서를 알아본 후에 문제를 해결해 보도록 하자.

   문제를 해결하는 방법은 '완전탐색'을 이용해 주었다. 모든 경우를 다해보고 결과를 출력하는 방법이다.

   먼저 문제를 이해하면서 우리가 무엇 무엇을 구현해야 하는지 알아보자.

   1. 주어진 판들은 자유롭게 회전할 수 있다. 그러나 뒤집을 수는 없다.

   - 가장 처음에 나온 문제 조건이다. 요놈부터 상당히 골때린다. 천천히 생각을 해보자. 총 5개의 판이 있고, 각 판은

    90 / 180 / 270 / 360 도로 회전이 가능하다. 그렇다면 판을 쌓는 순서는 고려하지 않고, 판을 회전하는 경우만 존재했다고

    생각했을 때 몇 가지 경우가 존재할까???

    4 x 4 x 4 x 4 x 4 가지 경우가 존재할 것이다... 왜???

    (지금부터 글쓴이의 편의를 위해 90 = 1도회전, 180 = 2도회전, 270 = 3도회전, 360 = 4도회전 이라고 하겠다 ! )

    { 1층판, 2층판, 3층판, 4층판, 5층판 } 이 있다고 생각했을 때 대략 몇개만 적어본다면

    { 1도회전, 4도회전, 3도회전, 4도회전, 2도회전 } , { 3도회전, 3도회전, 3도회전, 2도회전, 1도회전 } ,

    { 4도회전, 2도회전, 2도회전, 1도회전, 3도회전 } ............................................ 

    뭐 이런식으로 쭉 경우가 있을 것이다. 즉 간략하게 적어보면 '도회전' 이라는 단어를 빼고 경우를 적어본다면

    { 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 2 }, { 1, 1, 1, 1, 3 } ................................................................. { 4, 4, 4, 4, 4 } 까지 경우가

    존재할 것이다. 어디서 많이 본 나열같다. 바로 중복순열이다. 4개의 값(1, 2, 3, 4도회전) 중에서 5개를 뽑아서 중복순열로

    쭉 나열한다면 저런 값이 나올 것이다.

   

   본인이 실제 4개중에 5개를 뽑는 중복순열을 구현해서 실행한 결과이다. 우리가 해내야 하는 것이 바로 이것이다.

   즉, 각 층마다 판을 회전 시킬 수 있다는 것은 "4개중에 5개를 뽑는 중복순열을 구현하면 된다!" 라는 것이다.

   아직 중복순열에 대한 구현법을 잘 모른다면 아래의 링크를 타고 글을 한번 읽어보고 오도록 하자.

   [ 중복순열 알아보기(Click) ]

   2.회전을 완료한 후 참가자는 판 5개를 쌓는다. 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다.

  - 두번째 조건이다. 어떻게 어떻게 해서 판 회전시키는 거를 다 구해놨더니 이제는 판을 자유롭게 쌓을 수 있단다..

     그렇다면 { 1층에 들어갈 판의번호, 2층.. , 3층.. , 4층.. , 5층.. } 을 본다면 아마 이런 경우가 존재할 것이다.

     { 1, 2, 3, 4, 5 } , { 4, 2, 3, 5, 1 } , { 3, 5, 2 ,1, 4 } , { 5, 2, 3, 4, 1 }.....

     이건 잘보면.... 순열과 비슷하다. 5개를 순서대로 나열하는 순열을 구현한다면 아래와 같은 결과가 나오게 된다.

     

     즉, 우리는 판을 쌓는 순서를 자유롭게 한다는 것은 "5개 중에 5개를 뽑는 순열로 구현하면 된다!" 라는 것이다.

    3. 가장 적은 횟수로 미로를 탈출한 사람이 우승한다.

    - 이 부분은 BFS탐색을 통해서 구현해 주었다. 물론, 고려해주어야 할 것이, 만약 미로의 입구 혹은 출구가 막힌 경우에는

      탈출할 수 없다는 것으로 간주한다고 했으니, 미로의 (0,0,0)과 (4,4,4)는 1이여야 한다는 것이다.

2) 우리가 지금까지 한 것은 중복순열과 순열을 이용해서 미로를 임의의 순서대로 쌓으면서 임의로 회전하는 경우를 모두

   구했다. 그렇다면 이제 BFS로 최단거리만 구해주면될까? 아니다. 우리는 지금까지 몇 번째 미로를 몇 층에 쌓을 것인지

   그 미로를 몇도 회전할 것인지에 대해서만 저장해 놓았을 뿐 실제로 미로를 회전하고 쌓는 부분은 구현하지 않았다.

   회전하는 것은 이 글을 읽는 분들의 편의를 위해서 공식을 적어두겠다.

시계방향 90도 회전 하는 경우

- MAP[x][y] 가 MAP[y][4-x] 로 가게됨.

- 즉, MAP[x][y] = 0 이 였다면 시계 방향으로 90도 회전한 맵에서는 MAP[y][4-x]가 0이 된다.

시계방향 180도 회전 하는 경우

- MAP[x][y]가 MAP[4-x][4-y]로 가게됨.

- 즉, MAP[x][y] = 0 이 였다면 시계 방향으로 180도 회전한 맵에서는 MAP[4-x][4-y]가 0이 된다.

시계방향 270도 회전 하는 경우

- MAP[x][y]가 MAP[4-y][x]로 가게됨.

- 즉, MAP[x][y] = 0 이 였다면 시계 방향으로 270도 회전한 맵에서는 MAP[4-y][x]가 0이 된다.

   사실 위의 내용은 조금만 생각한다면 누구나 알아낼 수 있는 것이다. 또한, 위의 방법처럼이 아닌

   90도 회전한 방법만 알아낸 후에, 180도는 90도 + 90도, 270도는 90 + 90 + 90 도로 구현해도 무관하다.

   그럼 이제 미로 회전도 시켰고 미로를 쌓기만 하고 BFS탐색을 통해서 최단거리만 구하면 된다.

   이 때, 가장 중요한 것은 "맵의 복사"이다. 맵을 하도 돌리고 순서를 뒤죽박죽으로 만드는 것을 반복하다 보니 원본의 맵이

   손상되기가 쉽다. 즉, 맵을 복사해서 임의의 맵에서 모든 작업을 하도록 하자 !

3) 문제가 문제인지라 본인의 소스코드도 상당히 길다. 본인이 사용한 변수명과 본인의 코드가 어떻게 흘러가는지 간략하게

   설명하고 소스코드를 참고하도록 하자.

[ 사용한 핵심 배열 및 변수 List ]

1. int MAP[MAX][MAX][MAX]   

- 원본의 맵이다. 절대 손상되어서는 안되는 원본의 맵 !

2. int C_MAP[MAX][MAX][MAX]   

- 임시적인 맵이다. 이 맵을 가지고 모든 계산을 다 해준다.

3. Maze_Order[MAX]           

- 미로의 순서를 저장해주는 배열이다.

- 이 배열에 우리가 순열을 통해서 구해준 미로의 순서 { 2, 3, 4, 1, 5 } 와 같은 순서를 저장해 둔다.

4. Turn_Order[MAX]

- 미로의 회전할 각도를 저장해주는 배열이다.

- 쉽게 구현하기 위해서 0 = 360도회전, 1 = 90도 회전, 2 = 180도 회전, 3 = 270도 회전으로 표시했다.

- 예를 들어서 Turn_Order[0~5]의 값이 { 0, 3, 2, 2, 1 } 이라면 이는

  1층미로는 360도회전, 2층미로는 270도회전, 3층과 4층미로는 180도 회전, 5층 미로는 90도회전 이라는 의미이다.

[ 사용한 핵심 함수 List ]

1. Make_Maze_Order(int Cnt)

- 미로를 쌓을 순서를 정해주는 함수이다. 위에서 말했듯이 재귀를 이용한 순열 구현법으로 구현하였다.

- 여기서 정해진 미로의 순서가 Maze_Order[] 배열에 순차적으로 저장된다.

2. Make_Maze_Turn_Order(int Cnt)

- 미로를 회전할 순서를 정해주는 함수이다. 위에서 말했뜻이 재귀를 이용한 중복순열 구현법을 구현하였다.

- 여기서 정해진 미로가 회전할 각도(0,1,2,3으로 표현)가 Turn_Order[] 배열에 순차적으로 저장된다.

3. Make_Maze()

- 정해진 순서와 정해진 회전할 각도에 따라서 실제 미로를 만드는 함수이다.

- 위에서 말했듯이 "임의의 맵"에다가 구현해줘야 한다.

- 구현 방법은 먼저 초기에 임의의맵에 모두 "1"의 값을 넣어준 후에, 원래의 맵에서 0인 부분만 회전시켜서 넣어주었다.

4. BFS(int A[][][])

- 가장 마지막 단계인 미로 탈출을 위한 최단거리를 구하는 함수이다.

마지막으로 본인의 코드가 진행되는 순서를 말하고 소스코드를 공개하겠다. 하나 이해해줘야 할 것이...

왜 그랬는지는 모르겠는데, 문제에 "회전을 완료한 후에 참가자는 판 5개를 쌓는다" 라고 되어 있는데 지금보니 본인 코드에서는

판을 먼저 쌓아놓고 그 판들을 회전시키도록 순서를 반대로 구현해주었다. 뭐 결과에는 크게 상관이 없으니 무튼 이부분 명심하면서 코드를 보도록 하자.

[ 코드 진행 순서 ]

1. Solve() 함수에서 Input() 함수를 통해 입력받은 후, Solution() 함수로 들어가서 본격적 구현 시작.

2. Solution() 함수에서 Make_Maze_Order(0) 함수를 호출함으로써 미로의 순서를 정해주는 함수 호출.

   사실 이 Makze_Maze_Order(0) 위에 Check_MAP_State()라는 함수를 호출하는 부분이 있는데 이 부분은 본인이

   개인적으로 추가구현을 한 부분이다. 이 부분은 입력받은 맵이 전부 0이거나 전부 1일 경우에 바로 답을 출력한다.

   사실 모두 0이라면 이러한 재귀들을 다 필요없이 무조건 답이 -1이고, 전부 1일 경우 이러한 재귀들 다 필요없이

   답이 무조건 12이기 때문이다. (0,0,0)에서 (4,4,4)까지 가는데 걸리는 최단거리 = 12

3. Make_Maze_Order() 함수에서 5개 판에 대한 순서를 모두 정했다면 Make_Maze_Turn_Order(0) 함수를 호출함으로

   써 미로의 회전방향을 정해주는 함수 호출.

4. Make_Maze_Turn_Order() 함수에서 5개 판에 대한 회전 순서가 모두 정해졌다면 Make_Maze() 함수를 호출함으로

   써 임의의 맵에다가 주어진 순서와 회전순서에 맞게 미로 제작.

5. 미로제작이 완료되었다면 (0, 0, 0)과 (4, 4, 4) 가 갈 수 있는 곳인 "1"인지 판단 후, BFS() 함수를 호출함으로써

   걸리는 시간 계산. 이 결과값이 기존의 값보다 더 작다면 결과값 갱신.

6. 이 후에는 재귀의 반복.

   미로 순서 정해주기 -> 미로 회전방향 정해주기 -> 미로제작 -> 최단거리 찾기가 반복됬으므로

   한번 최단거리를 찾았다면, 그 다음 재귀는 미로 회전방향 정해주기로 다시 가서 다른 방향으로 회전 후 반복.

   모든 방향에 대해서 회전을 다 해줬다면 미로 순서 정해주기로 돌아가서 다른 순서로 정해주고 다시 반복.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<cstring>
 
#define endl "\n"
#define MAX 5
using namespace std;
 
int MAP[MAX][MAX][MAX];
int C_MAP[MAX][MAX][MAX];
int Maze_Order[MAX];
int Turn_Order[MAX];
bool Select[MAX];
bool Visit[MAX][MAX][MAX];
int Answer = 987654321;
 
int dx[] = { 0, 0, 1, -1, 0, 0 };
int dy[] = { 1, -1, 0, 0, 0, 0 };
int dh[] = { 0, 0, 0, 0, 1, -1 };
 
void Input()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            for (int k = 0; k < MAX; k++)
            {
                cin >> MAP[i][j][k];
            }
        }
    }
 
    for (int i = 0; i < MAX; i++)
    {
        Maze_Order[i] = -1;
        Turn_Order[i] = -1;
    }
}
 
void Copy_MAP()
{
    for (int i = 0; i < MAX; i++)
    {
        int Idx = Maze_Order[i];
        for (int j = 0; j < MAX; j++)
        {
            for (int k = 0; k < MAX; k++)
            {
                C_MAP[i][j][k] = MAP[Idx][j][k];
            }
        }
    }
}
 
void Actual_Turning(int T, int Idx)
{
    if (T == 0) return;
    else if (T == 1)
    {
        for (int i = 0; i < MAX; i++)
        {
            for (int j = 0; j < MAX; j++)
            {
                if (i == j) continue;
                if (MAP[Idx][i][j] == 0)
                {
                    C_MAP[Idx][4 - j][i] = 0;
                    C_MAP[Idx][i][j] = 1;
                }
            }
        }
    }
    else if (T == 2)
    {
        for (int i = 0; i < MAX; i++)
        {
            for (int j = 0; j < MAX; j++)
            {
                if (i == j) continue;
                if (MAP[Idx][i][j] == 0)
                {
                    C_MAP[Idx][4 - i][4 - j] = 0;
                    C_MAP[Idx][i][j] = 1;
                }
            }
        }
    }
    else if (T == 3)
    {
        for (int i = 0; i < MAX; i++)
        {
            for (int j = 0; j < MAX; j++)
            {
                if (i == j) continue;
                if (MAP[Idx][i][j] == 0)
                {
                    C_MAP[Idx][j][4 - i] = 0;
                    C_MAP[Idx][i][j] = 1;
                }
            }
        }
    }
}
 
int BFS(int A[MAX][MAX][MAX])
{
    queue<pair<pair<int, int>, pair<int, int>>> Q;
    Q.push(make_pair(make_pair(0, 0), make_pair(0, 0)));
    Visit[0][0][0] = true;
    
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int h = Q.front().second.first;
        int Cnt = Q.front().second.second;
        Q.pop();
 
        if (x == MAX - 1 && y == MAX - 1 && h == MAX - 1)
        {
            return Cnt;
        }
 
        for (int i = 0; i < 6; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nh = h + dh[i];
 
            if (nx >= 0 && ny >= 0 && nh >= 0 && nx < MAX && ny < MAX && nh < MAX)
            {
                if (A[nh][nx][ny] == 1 && Visit[nh][nx][ny] == false)
                {
                    Visit[nh][nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(nh, Cnt + 1)));
                }
            }
        }
    }
    return -1;
}
 
void Make_Maze()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            for (int k = 0; k < MAX; k++)
            {
                C_MAP[i][j][k] = 1;
            }
        }
    }
 
    for (int i = 0; i < MAX; i++)
    {
        int Idx = Maze_Order[i];
        int Turn = Turn_Order[i];
 
        if (Turn == 0)
        {
            for (int x = 0; x < MAX; x++)
            {
                for (int y = 0; y < MAX; y++)
                {
                    C_MAP[i][x][y] = MAP[Idx][x][y];
                }
            }
        }
        else if (Turn == 1)
        {
            for (int x = 0; x < MAX; x++)
            {
                for (int y = 0; y < MAX; y++)
                {
                    if (MAP[Idx][x][y] == 0)
                    {
                        C_MAP[i][y][4 - x] = 0;
                    }
                }
            }
        }
        else if (Turn == 2)
        {
            for (int x = 0; x < MAX; x++)
            {
                for (int y = 0; y < MAX; y++)
                {
                    if (MAP[Idx][x][y] == 0)
                    {
                        C_MAP[i][4 - x][4 - y] = 0;
                    }
                }
            }
        }
        else if (Turn == 3)
        {
            for (int x = 0; x < MAX; x++)
            {
                for (int y = 0; y < MAX; y++)
                {
                    if (MAP[Idx][x][y] == 0)
                    {
                        C_MAP[i][4 - y][x] = 0;
                    }
                }
            }
        }
    }
}
 
void Make_Maze_Turn_Order(int Cnt)
{
    if (Cnt == MAX)
    {
        Make_Maze();
        if (C_MAP[0][0][0] == 1 && C_MAP[4][4][4] == 1)
        {
            memset(Visit, false, sizeof(Visit));
            int Temp_Result = BFS(C_MAP);
            if (Temp_Result != -1)
            {
                if (Temp_Result < Answer) Answer = Temp_Result;
            }
        }
        return;
    }
 
    for (int Turn = 0; Turn < 4; Turn++)
    {
        Turn_Order[Cnt] = Turn;
        Make_Maze_Turn_Order(Cnt + 1);
    }
}
 
void Make_Maze_Order(int Cnt)
{
    if (Cnt == MAX)
    {
        Make_Maze_Turn_Order(0);
        return;
    }
 
    for (int i = 0; i < 5; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        Maze_Order[i] = Cnt;
        Make_Maze_Order(Cnt + 1);
        Maze_Order[i] = -1;
        Select[i] = false;
    }
}
 
pair<int, bool> Check_MAP_State()
{
    pair<int, bool> Temp;
    bool Flag;
 
    for (int Idx = 0; Idx < 2; Idx++)
    {
        Flag = true;
        for (int i = 0; i < MAX; i++)
        {
            for (int j = 0; j < MAX; j++)
            {
                for (int k = 0; k < MAX; k++)
                {
                    if (MAP[i][j][k] != Idx)
                    {
                        Flag = false;
                        break;
                    }
                }
                if (Flag == false) break;
            }
            if (Flag == false) break;
        }
 
        if (Flag == true)
        {
            Temp.first = Idx;
            Temp.second = Flag;
            return Temp;
        }
    }
    Temp.first = -1;
    Temp.second = false;
    return Temp;
}
 
void Solution()
{
    pair<int, bool> Temp;
    Temp = Check_MAP_State();
    if (Temp.second == true)
    {
        if (Temp.first == 0)
        {
            cout << -1 << endl;
            return;
        }
        else
        {
            cout << "12" << endl;
            return;
        }
    }
    Make_Maze_Order(0);
    if (Answer == 987654321) Answer = -1;
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}