2 x 2 x 2 루빅 큐브

Sonny은 아마도 루빅 큐브를 풀지 못하는 유일한 컴퓨터과학 박사과정 학생일 것이다. 어느 날 그는 작고 깔끔한 2 x 2 x 2 루빅 큐브를 발견하고 "드디어 나도 풀 수 있을 만큼 쉬운 큐브다!"라고 생각했다. 하지만 그것은 착각이었고, 그는 보기 좋게 실패했다. 정말 창피한 일이다.

이런 일이 다시는 없도록, 그는 큐브를 푸는 프로그램을 작성하기로 했다. 그러다 기발한 생각이 떠올랐다. 직접 하는 대신 프로그래밍 대회 참가자들에게 시키면 어떨까? 그래서 2 x 2 x 2 루빅 큐브의 초기 상태가 주어지면, 그 큐브를 얼마나 빨리 풀 수 있는지 알아내는 것이 이 문제의 과제다.

이 미니 큐브는 6개의 면을 가지며, 각 면에는 4개의 색칠된 타일이 있다. 각 면은 아래 그림처럼 앞(F), 뒤(B), 위(U), 아래(D), 왼쪽(L), 오른쪽(R)으로 표시된다. 각 타일의 색은 빨강(R), 초록(G), 파랑(B), 노랑(Y), 주황(O), 하양(W) 중 하나이며, 각 색은 정확히 4개씩 있다. 모든 면에서 네 타일의 색이 같아지면 큐브가 풀린 것이다.

큐브를 변형하기 위해 세 가지 서로 다른 회전을 자유롭게 조합할 수 있다: X축 회전, Y축 회전, Z축 회전이다. 각 회전은 큐브의 절반을 아래 그림에 표시된 방향으로 정확히 90도 돌린다. 뒤-아래-왼쪽 꼭짓점은 모든 유효한 회전에서 고정되어 있으므로, 각 축마다 회전 방향은 정확히 하나뿐이다.

주어진 상태에서 큐브를 푸는 데 필요한 최소 회전 횟수는 얼마인가?

각 면의 색을 펼쳐 놓은("펼친") 큐브 지도가 다음 형식으로 주어진다:

..UU....
..UU....
LLFFRRBB
LLFFRRBB
..DD....
..DD....

위 글자들은 각 면의 색이 지도에서 어디에 나타나는지를(첫 번째 그림과 같은 방식으로) 보여 주는 범례일 뿐이며, 실제 입력이 아니다. 앞면은 그림과 같은 방향으로 놓이고, 나머지 면들은 지도가 큐브 전체를 감싸도록 그 주위에 붙는다. 실제 지도에서 타일 글자는 R, G, B, Y, O, W 중 하나다. 점(.) 문자는 지도를 6 x 8 격자로 채우기 위한 것이며 그 밖의 의미는 없다.

입력에는 이 형식의 큐브 지도가 여러 개 들어 있고, 각 지도는 빈 줄로 구분된다. 모든 상태는 유효하며 풀 수 있다. 입력의 끝은 오직 '.' 문자로만 이루어진 "빈" 상태로 표시되며, 그 지도는 처리하지 않는다.

각 큐브에 대해, 그 큐브를 푸는 데 필요한 최소 회전 횟수를 한 줄에 하나씩 출력한다. 한 번의 회전은 X, Y, Z축 중 하나를 기준으로 위에 표시된 고정된 방향으로 90도 돌리는 것이다. 큐브가 이미 풀려 있다면 0을 출력한다.