PS/Implementation
백준 5373번: 큐빙 (JAVA)
닻과매
2022. 4. 2. 09:03
https://www.acmicpc.net/problem/5373
5373번: 큐빙
각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란
www.acmicpc.net
문제
루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다.
큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다.
이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란색, 앞 면은 빨간색, 뒷 면은 오렌지색, 왼쪽 면은 초록색, 오른쪽 면은 파란색이다.
루빅스 큐브를 돌린 방법이 순서대로 주어진다. 이때, 모두 돌린 다음에 가장 윗 면의 색상을 구하는 프로그램을 작성하시오.
위의 그림은 루빅스 큐브를 푼 그림이다. 왼쪽 면은 시계방향으로 조금 돌려져 있는 상태이다.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다. 각 테스트 케이스는 다음과 같이 구성되어져 있다.
- 첫째 줄에 큐브를 돌린 횟수 n이 주어진다. (1 ≤ n ≤ 1000)
- 둘째 줄에는 큐브를 돌린 방법이 주어진다. 각 방법은 공백으로 구분되어져 있으며, 첫 번째 문자는 돌린 면이다. U: 윗 면, D: 아랫 면, F: 앞 면, B: 뒷 면, L: 왼쪽 면, R: 오른쪽 면이다. 두 번째 문자는 돌린 방향이다. +인 경우에는 시계 방향 (그 면을 바라봤을 때가 기준), -인 경우에는 반시계 방향이다.
출력
각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란색은 y, 빨간색은 r, 오렌지색은 o, 초록색은 g, 파란색은 b.
풀이
삼성 A형 기출이라는데, 이게 A형? 시험장에서 본 사람들은 멘붕이 왔을 듯하다.
돌리는 연산은
1) 돌리는 판과 인접한 네 면의 12개 element가 3칸씩(혹은 9칸씩) 이동하며
2) 돌리는 판의 가장자리 8개의 element가 2칸씩(혹은 6칸씩) 이동한다.
이를 구현해주면 되는데, 유의할 점으로는
1) 기준을 확실하게 잡아야 한다: 안 그러면 본인이 헷갈리며, 디버깅 늪에 빠짐
모든 rotation에 대해 index를 한 번에 처리할 수 있는 방법이 있는데, 나는 생각하지 못하여 각 케이스마다 하드코딩을 했다. 8448바이트의 승리!
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
public class Baekjoon5373_큐빙 {
static char[][] up = new char[][] {{'w', 'w', 'w'}, {'w', 'w', 'w'}, {'w', 'w', 'w'}},
down = new char[][] {{'y', 'y', 'y'}, {'y', 'y', 'y'}, {'y', 'y', 'y'}},
front = new char[][] {{'r', 'r', 'r'}, {'r', 'r', 'r'}, {'r', 'r', 'r'}},
back = new char[][] {{'o', 'o', 'o'}, {'o', 'o', 'o'}, {'o', 'o', 'o'}},
left = new char[][] {{'g', 'g', 'g'}, {'g', 'g', 'g'}, {'g', 'g', 'g'}},
right = new char[][] {{'b', 'b', 'b'}, {'b', 'b', 'b'}, {'b', 'b', 'b'}};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
String order = st.nextToken();
char command = order.charAt(0), dir = order.charAt(1);
rotate(command, dir);
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
sb.append(up[i][j]);
}
sb.append("\n");
}
}
System.out.println(sb.toString());
}
static void rotate(char command, char dir) {
int num = (dir == '+')? 3: 9;
int num2 = (dir == '+')? 2: 6;
Queue<Character> queue = new ArrayDeque<>();
Queue<Character> queue2 = new ArrayDeque<>();
switch (command) {
case 'U':
for (int i = 0; i < 3; i++) queue.offer(front[0][i]);
for (int i = 0; i < 3; i++) queue.offer(right[0][i]);
for (int i = 0; i < 3; i++) queue.offer(back[0][i]);
for (int i = 0; i < 3; i++) queue.offer(left[0][i]);
queue2.offer(up[2][0]);
queue2.offer(up[2][1]);
queue2.offer(up[2][2]);
queue2.offer(up[1][2]);
queue2.offer(up[0][2]);
queue2.offer(up[0][1]);
queue2.offer(up[0][0]);
queue2.offer(up[1][0]);
for (int i = 0; i < num; i++) {
queue.offer(queue.poll());
}
for (int i = 0; i < num2; i++) {
queue2.offer(queue2.poll());
}
for (int i = 0; i < 3; i++) front[0][i] = queue.poll();
for (int i = 0; i < 3; i++) right[0][i] = queue.poll();
for (int i = 0; i < 3; i++) back[0][i] = queue.poll();
for (int i = 0; i < 3; i++) left[0][i] = queue.poll();
up[2][0] = queue2.poll();
up[2][1] = queue2.poll();
up[2][2] = queue2.poll();
up[1][2] = queue2.poll();
up[0][2] = queue2.poll();
up[0][1] = queue2.poll();
up[0][0] = queue2.poll();
up[1][0] = queue2.poll();
break;
case 'D':
for (char[][] temp: new char[][][] {back, right, front, left}) {
for (int i = 0; i < 3; i++) {
queue.offer(temp[2][i]);
}
}
queue2.offer(down[2][0]);
queue2.offer(down[2][1]);
queue2.offer(down[2][2]);
queue2.offer(down[1][2]);
queue2.offer(down[0][2]);
queue2.offer(down[0][1]);
queue2.offer(down[0][0]);
queue2.offer(down[1][0]);
for (int i = 0; i < num; i++) {
queue.offer(queue.poll());
}
for (int i = 0; i < num2; i++) {
queue2.offer(queue2.poll());
}
for (char[][] temp: new char[][][] {back, right, front, left}) {
for (int i = 0; i < 3; i++) {
temp[2][i] = queue.poll();
}
}
down[2][0] = queue2.poll();
down[2][1] = queue2.poll();
down[2][2] = queue2.poll();
down[1][2] = queue2.poll();
down[0][2] = queue2.poll();
down[0][1] = queue2.poll();
down[0][0] = queue2.poll();
down[1][0] = queue2.poll();
break;
case 'F':
for (int i = 0; i < 3; i++) queue.offer(down[2][2-i]);
for (int i = 0; i < 3; i++) queue.offer(right[2-i][0]);
for (int i = 0; i < 3; i++) queue.offer(up[2][2-i]);
for (int i = 0; i < 3; i++) queue.offer(left[i][2]);
queue2.offer(front[2][0]);
queue2.offer(front[2][1]);
queue2.offer(front[2][2]);
queue2.offer(front[1][2]);
queue2.offer(front[0][2]);
queue2.offer(front[0][1]);
queue2.offer(front[0][0]);
queue2.offer(front[1][0]);
for (int i = 0; i < num; i++) {
queue.offer(queue.poll());
}
for (int i = 0; i < num2; i++) {
queue2.offer(queue2.poll());
}
for (int i = 0; i < 3; i++) down[2][2-i] = queue.poll();
for (int i = 0; i < 3; i++) right[2-i][0] = queue.poll();
for (int i = 0; i < 3; i++) up[2][2-i] = queue.poll();
for (int i = 0; i < 3; i++) left[i][2] = queue.poll();
front[2][0] = queue2.poll();
front[2][1] = queue2.poll();
front[2][2] = queue2.poll();
front[1][2] = queue2.poll();
front[0][2] = queue2.poll();
front[0][1] = queue2.poll();
front[0][0] = queue2.poll();
front[1][0] = queue2.poll();
break;
case 'B':
for (int i = 0; i < 3; i++) queue.offer(down[0][i]);
for (int i = 0; i < 3; i++) queue.offer(left[2-i][0]);
for (int i = 0; i < 3; i++) queue.offer(up[0][i]);
for (int i = 0; i < 3; i++) queue.offer(right[i][2]);
queue2.offer(back[2][0]);
queue2.offer(back[2][1]);
queue2.offer(back[2][2]);
queue2.offer(back[1][2]);
queue2.offer(back[0][2]);
queue2.offer(back[0][1]);
queue2.offer(back[0][0]);
queue2.offer(back[1][0]);
for (int i = 0; i < num; i++) {
queue.offer(queue.poll());
}
for (int i = 0; i < num2; i++) {
queue2.offer(queue2.poll());
}
for (int i = 0; i < 3; i++) down[0][i] = queue.poll();
for (int i = 0; i < 3; i++) left[2-i][0] = queue.poll();
for (int i = 0; i < 3; i++) up[0][i] = queue.poll();
for (int i = 0; i < 3; i++) right[i][2] = queue.poll();
back[2][0] = queue2.poll();
back[2][1] = queue2.poll();
back[2][2] = queue2.poll();
back[1][2] = queue2.poll();
back[0][2] = queue2.poll();
back[0][1] = queue2.poll();
back[0][0] = queue2.poll();
back[1][0] = queue2.poll();
break;
case 'L':
for (int i = 0; i < 3; i++) queue.offer(down[i][2]);
for (int i = 0; i < 3; i++) queue.offer(front[2-i][0]);
for (int i = 0; i < 3; i++) queue.offer(up[2-i][0]);
for (int i = 0; i < 3; i++) queue.offer(back[i][2]);
queue2.offer(left[2][0]);
queue2.offer(left[2][1]);
queue2.offer(left[2][2]);
queue2.offer(left[1][2]);
queue2.offer(left[0][2]);
queue2.offer(left[0][1]);
queue2.offer(left[0][0]);
queue2.offer(left[1][0]);
for (int i = 0; i < num; i++) {
queue.offer(queue.poll());
}
for (int i = 0; i < num2; i++) {
queue2.offer(queue2.poll());
}
for (int i = 0; i < 3; i++) down[i][2] = queue.poll();
for (int i = 0; i < 3; i++) front[2-i][0] = queue.poll();
for (int i = 0; i < 3; i++) up[2-i][0] = queue.poll();
for (int i = 0; i < 3; i++) back[i][2] = queue.poll();
left[2][0] = queue2.poll();
left[2][1] = queue2.poll();
left[2][2] = queue2.poll();
left[1][2] = queue2.poll();
left[0][2] = queue2.poll();
left[0][1] = queue2.poll();
left[0][0] = queue2.poll();
left[1][0] = queue2.poll();
break;
case 'R':
for (int i = 0; i < 3; i++) queue.offer(down[2-i][0]);
for (int i = 0; i < 3; i++) queue.offer(back[2-i][0]);
for (int i = 0; i < 3; i++) queue.offer(up[i][2]);
for (int i = 0; i < 3; i++) queue.offer(front[i][2]);
queue2.offer(right[2][0]);
queue2.offer(right[2][1]);
queue2.offer(right[2][2]);
queue2.offer(right[1][2]);
queue2.offer(right[0][2]);
queue2.offer(right[0][1]);
queue2.offer(right[0][0]);
queue2.offer(right[1][0]);
for (int i = 0; i < num; i++) {
queue.offer(queue.poll());
}
for (int i = 0; i < num2; i++) {
queue2.offer(queue2.poll());
}
for (int i = 0; i < 3; i++) down[2-i][0] = queue.poll();
for (int i = 0; i < 3; i++) back[2-i][0] = queue.poll();
for (int i = 0; i < 3; i++) up[i][2] = queue.poll();
for (int i = 0; i < 3; i++) front[i][2] = queue.poll();
right[2][0] = queue2.poll();
right[2][1] = queue2.poll();
right[2][2] = queue2.poll();
right[1][2] = queue2.poll();
right[0][2] = queue2.poll();
right[0][1] = queue2.poll();
right[0][0] = queue2.poll();
right[1][0] = queue2.poll();
break;
}
}
}