백준(BOJ) 16985번 - Maaaaaaaaaze

문제 : https://www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

풀이 :

 

크기가 y =5 x = 5 z = 1인 블럭이 5개 있다.

 

이 블럭들의 순서는 next_permutation 함수를 통해서 01234 부터 ~ 43210 까지의 순서들로

각각 처리해주어야 한다.

( 5! 으로 120가지 경우의 수 )

 

순서가 정해진 블럭은 5x5x5 정육면체이다. 이 정육면체는 블럭5개가 합쳐있는 것이고

각각의 블럭은 회전해야 한다. 이를 재귀적으로 구현해주자. 

 

예를들면  위에 블럭부터 0번 회전 // 0번 회전 // 0번 회전 // 0번 회전 // 0번 회전 부터

4번 회전 // 4번 회전 // 4번 회전 // 4번 회전 // 4번 까지의 경우의 수를 모두 구해주어야 한다.

(4^n 개로 256경우의수)

 

경우의 수를 구할때는 BFS를 통해 정육면체의 0,0,0 부터 4,4,4,까지 가는 최소 경로를 구해주면 된다.

(N^3)

 

코드( C ++ )