[백준 / BOJ] 16985 Maaaaaaaaaze

문제

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

16985번: Maaaaaaaaaze

미로를 나타내는 5*5크기의 판이 5개 주어진다.

판의 각 칸에는 이동할수없는칸 0, 이동할수있는칸 1이 있다.

5개의 판은 자유롭게 쌓을수있고 각 판마다 자유롭게 90도 회전또한 가능하다.

이때, 판을 적절히 쌓고 적절히 회전해서 5*5*5크기의 미로를 탈출하는 최소 이동횟수를 구하는 문제다.

 

입구는 5*5*5크기의 그리드의 각 모서리이며 출구는 입구와 면을 공유하지않는 모서리이다.

 

 

문제

BFS와 백트래킹을 이용한 완전탐색으로 풀었다.

최악의경우 걸리는 시간을 계산하는게 중요했던 문제였다.

걸리는 시간을 계산해보면,

 

1. 판을 자유롭게 쌓는 경우의 수 

- 쌓을수있는 판이 총 5개 이므로, 5! = 120

 

2. 자유롭게 쌓은 판을 회전하는 경우의 수

- 회전하는 형태는 판마다 4개가 있으므로 4^5 = 1024

 

3. 회전했을때, 미로를 탐색하는 반복횟수 

- 미로의 칸은 총 125칸이므로 5*5*5 = 125

 

4. 탐색한 미로의 체크배열을 초기화 하는 반복횟수

- 3번과 마찬가지로 125

 

위 4가지를 모두 곱할경우 약 20억이 나온다. 

시간안에 탐색을 완료하기위해서 위 과정에서 걸리는시간을 줄여야한다.

각 과정마다 시간을 줄이는 방법은 다음과 같다.

 

1. 판을 자유롭게 쌓는 경우의 수

- 판을 쌓는 형태는 총 5!가지 이지만, 겹치는 형태를 제거하여 탐색횟수를 줄일수있다.

예를들어, 입력순으로 1,2,3,4,5번째 칸이라 할때, 위에서부터 1 2 3 4 5로 미로를 만드는것과 5 4 3 2 1로 미로를 만드는것은 같은 결과를 반환할것이다. 

 

2. 자유롭게 쌓은 판을 회전하는 경우의 수

- 1번과 마찬가지로 겹치는 경우가 있다. 위에서부터 1,2,3,4,5칸이 순서대로 쌓여있다고 하자 1 2 3 4 5각 칸을 오른쪽으로 90도 회전한것은 결국 회전안한것과 같은 답을 반환한다. 마찬가지로 위에서부터 90도 180도 270도 360도 450도 회전한것은 180 270 360 450 540도 회전한것과 같은 결과를 반환한다.

 

3. 회전했을때, 미로를 탐색하는 반복횟수

- 모든경우에 대해서 시간을 줄일수는 없겠지만, 현재 탐색횟수가 이전까지 찾은 최소 탐색횟수보다 커진다면 종료하는식으로 구현해서 시간을 줄일수있다.

 

4. 탐색한 미로의 체크배열을 초기화 하는 반복횟수

- 초기화를 제외한경우 1번 2번 3번 경우의수를 모두 곱해도 int형 범위 안에 들어간다. 따라서 초기화할 필요없이 현재 탐색횟수로 체크를 해주면 4번 과정을 없앨수있다.

 

1번과 2번을 모두 구현하면 시간이 매우 줄어들겠지만, 4번만 구현해도 약 2천만번 반복으로 답을 구할수있다. 

따라서 최대 반복횟수는 120*1024*125 가 되서 완전탐색으로 풀수있다.

 

구현은 문제에서 시키는것을 그대로 구현하면 된다.

코드를 보며 이해하도록하자.

 

함수마다 한가지 역할을 수행하므로 이해하기 편할것?? 이다.

 

- turnMaze 함수는 입력받은 미로를 90도로 회전하는 역할을 한다.

 

- escape 함수는 만들어진 미로에서 밖으로 나갈수있는 최소 탐색횟수를 구한다.

 

- getMove 함수는 미로의 각층을 몇번 오른쪽으로 90도 회전시킬지 정하고 escape함수를 호출해 최소 탐색횟수를 반환한다.

 

- getFloor 함수는 미로를 쌓는 순서를 정하고 다 쌓았을경우 getMove함수를 호출한다.

 

- maze배열은 maze[층][90도 회전횟수][y][x] = 0 or 1 을 표현한다. 

 

- mazeForm배열은 각 층이 몇번 회전했는지 나타낸다.

 

- 덱 floor은 각 미로가 연결된 구조를 나타낸다 예를들어, 위에서부터 3 4 5 2 1 순으로 미로가 쌓였다면,

deq = {3, 4, 5, 2, 1}이 된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/16985%20Maaaaaaaaaze/main.cpp

devxb/JJUNalgo