알고리즘 풀이/백준(Boj)
백준(BOJ) 16985번 - Maaaaaaaaaze
100win10
2019. 11. 25. 01:51
문제 : https://www.acmicpc.net/problem/16985
16985번: Maaaaaaaaaze
첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다.
www.acmicpc.net
풀이 :
크기가 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 ++ )
