문제
루빅스 큐브(Rubik's Cube)는 퍼즐의 일종으로,
보통 작은 여러 개의 정육면체가 모여 만들어진 하나의 큰 정육면체 형태이며,
각 방향으로 돌아가게끔 만들어져서 흩어진 각 면의 색깔을 같은 색깔로 맞추는 것이다.
큐브 퍼즐은 1974년 헝가리의 루비크 에르뇌(Ernő Rubik)가 ‘마술 큐브(Magic cube)’라는 이름으로 발명하고,
1980년 루빅스 큐브라는 이름으로 처음 시판되었다.
루빅스 큐브를 맞춘다는 것은 보이는 면의 색을 동일하게 만든다는 의미를 지닌다.
루빅스 큐브가 돌면서 생기는 조합은 43,252,003,274,489,856,000 개이며,
이 수중 큐브를 다 맞출 수 있는 경우는 오직 이 수의 1/12 이다. - 출처 : wikipedia -
일반적으로 위 그림과 같은 3 * 3 * 3을 루빅스 큐브라고 한다. 임의의 섞인 3×3×3 큐브가 주어질 때 우리는 여러 단계를 거쳐 큐브를 맞추며,
그것은 해법에 따라 다르지만 40~100회전 정도라고 한다.
하지만 최적의 해법, 즉, 최소한의 회전으로 큐브를 맞추는 경우 아무리 복잡하게 섞는다고 해도 20번 이하에 맞출 수 있다고 한다. 이 20번이라는 수를 신의 수(God’s number)라고 하며 최소한의 회전으로 해결하는 방법을 신의 알고리즘(God’s Algorithm)이라고 한다.
90도의 회전만 허락하는 경우의 신의 수는 26번이라고 한다. 이제 우리가 큐브에 대한 신의 알고리즘에 도전해보자. 그런데 20번 또는 26번은 우리에게 너무 무리 일 것으로 생각 되므로 10번 이하에 해결할 수 있도록 섞인 경우만 다룬다고 가정한다. 또한 한 번 회전에는 각 면에 대하여 90도 시계방향과 반시계방향 회전만 허락한다고 가정한다. 또한 각 면의 가운데 열이나 행은 회전시키지 않는다고 가정한다. 따라서 각 면의 정 가운데는 고정된 상태이다.
섞여있는 큐브의 상태를 입력받아 최소의 횟수로 맞출 때 최소 몇 번의 회전으로 맞출 수 있을까?
입력
입력에 사용되는 문자는 ‘b’, ‘g’, ‘o’, ‘r’, ‘w’, ‘y’ 이고 각각 blue, green, orange, red, white, yellow를 의미한다.
입력 형식은 정육면체 전개도 모양으로 아래 입력 예를 참조한다. 적어도 한 번은 섞은 모양이 주어진다.
출력
1. 첫 행에 큐브를 맞출 때 최소의 회전수를 출력한다.
2. 다음 행부터 9행에 걸쳐 입력받은 큐브상태를 출력한다. 하나의 빈 행을 출력한다.
3. 다음 행부터 9행에 걸쳐 맞추기 위하여 처음 회전시킨 모습을 출력한다. 하나의 빈 행을 출력한다.
4. 3번 프로세스를 큐브를 다 맞춘 모습이 나올 때까지 반복한다.
예제 #1
b w w
b w w
b w w
o o o y b b r r r g g w
o o o y b b r r r g g w
o o o y b b r r r g g w
g y y
g y y
g y y
1
b w w
b w w
b w w
o o o y b b r r r g g w
o o o y b b r r r g g w
o o o y b b r r r g g w
g y y
g y y
g y y
w w w
w w w
w w w
o o o b b b r r r g g g
o o o b b b r r r g g g
o o o b b b r r r g g g
y y y
y y y
y y y
예제 #2
g w w
g w w
g w w
o o o w b b r r r g g y
o o o w b b r r r g g y
w b b r r r g g y o o o
b y y
b y y
b y y
2
g w w
g w w
g w w
o o o w b b r r r g g y
o o o w b b r r r g g y
w b b r r r g g y o o o
b y y
b y y
b y y
g w w
g w w
g w w
o o o w b b r r r g g y
o o o w b b r r r g g y
o o o w b b r r r g g y
b y y
b y y
b y y
w w w
w w w
w w w
o o o b b b r r r g g g
o o o b b b r r r g g g
o o o b b b r r r g g g
y y y
y y y
y y y
로그인해야 코드를 작성할 수 있어요.