16985. Maaaaaaaaaze

16985번: Maaaaaaaaaze

---

설명만 읽어도 감이 온다. 아.. 빡구현이구나. 엄청나게 귀찮을 것만 같은 느낌이 확 온다.

 

문제 자체는 크게 어렵지 않다. 다만 구현할 조건이 너무나도 많아서 문제.

1. 5×5 판 5개가 주어질 때,
2. 각 판을 임의로 회전한 후
3. 판을 쌓을 수 있는 모든 순서에 대해
4. 가능한 모든 입구-출구 쌍에 대해
5. 출구까지 도달하기 위한 이동 횟수의 최솟값을 구해야 한다.

보통의 브루트 포스 문제는 4~5번만 구현하면 되지만, 이 문제는.... 많다. 조건을 하나씩 해부해 보자.

판 회전

각 판을 임의의 방향으로 임의의 횟수만큼 회전할 수 있다. 풀이를 간단하게 만들기 위해 회전 방향은 시계 방향으로 고정하고, 각도는 0˚, 90˚, 180˚, 270˚ 중 하나로 정한다.

판 쌓기

5개의 판을 임의의 순서로 쌓을 수 있다. 총 $5! = 120$가지의 순서가 존재한다.

입구 - 출구 쌍

정육면체의 모든 꼭짓점이 입구가 될 수 있다. 입구가 정해지면 출구는 (대각선 반대편의 꼭짓점으로) 자동으로 정해진다. 총 8개의 쌍이 가능하다.

이동 횟수의 최솟값 구하기

정육면체에는 블럭이 $5^{3} = 125$개 존재한다. BFS로 구하면 된다.

---

위의 모든 조건을 종합해보자. 판을 회전하고, 쌓고, 입구와 출구를 정하고, 이동 횟수의 최솟값을 구하려면 최대 $4^{5} \times 5! \times 8 \times 125 = 122,880,000$번의 연산이 필요하다. 보통 1초에 1억 번의 연산이 가능하다고 하는데, 나는 Kotlin으로 구현해서 그런지 시간 초과를 받았다.

눈물

위의 조건을 최적화해 보자.

판 회전

판을 회전한 결과가 원래 판과 같다면 중복으로 탐색할 필요가 없다. 예를 들어 다음의 판은 어떻게 회전해도 항상 같다.

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

회전해서 같은 경우는 탐색하지 않아도 된다.

판 쌓기

같은 판이 여러 개 존재하는 경우, 판을 쌓았을 때 같은 정육면체가 나올 수 있다. 쌓았을 때 같은 경우는 탐색하지 않아도 된다.

입구 - 출구 쌍

판을 1 - 2 - 3 - 4 - 5 순서로 쌓고 입구를 (0, 0, 0), 출구를 (4, 4, 4)로 정하여 탐색한 경우와, 판을 5 - 4 - 3 - 2 - 1 순서로 쌓고 입구를 (4, 4, 4), 출구를 (0, 0, 0)으로 정하여 탐색한 경우는 완전히 같다. Z좌표가 0인 입구만 탐색해도 된다.

이동 횟수의 최솟값 구하기

주어진 정육면체에 대해 탐색만 하는 과정이므로 딱히 최적화할 부분이 없다.

---

힘들다 힘들어!! 하지만 구현 문제는 별다른 알고리즘이 필요 없는 만큼 이 정도 귀찮음은 감수해야 한다. 골3 주제에..

---

역대 최장 길이 코드인 듯?