큐빙

알고리즘 구분 : 구현, 시뮬레이션

문제

루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다.

큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다.

이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란색, 앞 면은 빨간색, 뒷 면은 오렌지색, 왼쪽 면은 초록색, 오른쪽 면은 파란색이다.

루빅스 큐브를 돌린 방법이 순서대로 주어진다. 이때, 모두 돌린 다음에 가장 윗 면의 색상을 구하는 프로그램을 작성하시오.

위의 그림은 루빅스 큐브를 푼 그림이다. 왼쪽 면은 시계방향으로 조금 돌려져 있는 상태이다.

입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다. 각 테스트 케이스는 다음과 같이 구성되어져 있다.

첫째 줄에 큐브를 돌린 횟수 n이 주어진다. (1 ≤ n ≤ 1000)
둘째 줄에는 큐브를 돌린 방법이 주어진다. 각 방법은 공백으로 구분되어져 있으며, 첫 번째 문자는 돌린 면이다. U: 윗 면, D: 아랫 면, F: 앞 면, B: 뒷 면, L: 왼쪽 면, R: 오른쪽 면이다. 두 번째 문자는 돌린 방향이다. +인 경우에는 시계 방향 (그 면을 바라봤을 때가 기준), -인 경우에는 반시계 방향이다.
출력
각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란색은 y, 빨간색은 r, 오렌지색은 o, 초록색은 g, 파란색은 b.

예제 입력 1
4
1
L-
2
F+ B+
4
U- D- L+ R+
10
L- U- L+ U- L- U- U- L+ U+ U+
예제 출력 1
rww
rww
rww
bbb
www
ggg
gwg
owr
bwb
gwo
www
rww

문제 풀이

큐브의 각 면을 3x3의 그래프로 보고, 정육면체이므로 [6][3][3]의 3차원 배열을 이용한 구현으로 풀었다.
직접 하드코딩을 통해 움직임을 일일이 구현했기에, 상당히 시간이 오래 걸리는 문제라고 할 수 있다.
큐브를 돌리는 과정을 일일이 확인하는 것은
https://rubiks-cube-solver.com/fr/ 이 사이트를 참고하면 된다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int t, n;
char start[6][3][3]  = {
    {
        {'w', 'w', 'w'},
        {'w', 'w', 'w'},
        {'w', 'w', 'w'}
    },
    {
        {'y', 'y', 'y'},
        {'y', 'y', 'y'},
        {'y', 'y', 'y'}
    },
    {
        {'r', 'r', 'r'},
        {'r', 'r', 'r'},
        {'r', 'r', 'r'}
    },
    {
        {'o', 'o', 'o'},
        {'o', 'o', 'o'},
        {'o', 'o', 'o'}
    },
    {
        {'g', 'g', 'g'},
        {'g', 'g', 'g'},
        {'g', 'g', 'g'}
    },
    {
        {'b', 'b', 'b'},
        {'b', 'b', 'b'},
        {'b', 'b', 'b'}
    }
}; // 윗, 아랫, 앞, 뒷, 왼쪽, 오른쪽 순의 큐브 원본
char cube[6][3][3];
char temp[6][3][3];
vector<string> moveDir;
void solve(string input); //큐브 돌리기
void topColor(); // 윗면 색상 출력

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> t;
    for(int i = 0; i < t; i++) {
        cin >> n;
        copy(&start[0][0][0], &start[0][0][0] + sizeof(start), &cube[0][0][0]);
        for(int j = 0; j < n; j++) {
            string input;
            cin >> input;
            solve(input);
        }
        topColor();
    }

    return 0;
}

void solve(string input) {
    // 움직이는 과정에서 필요한 temp 큐브에 값 복사
    copy(&cube[0][0][0], &cube[0][0][0] + sizeof(cube), &temp[0][0][0]);

    if(input[0] == 'U') {
        // 완료
        if(input[1] == '+') {
            temp[0][0][0] = cube[0][2][0];
            temp[0][0][1] = cube[0][1][0];
            temp[0][0][2] = cube[0][0][0];
            temp[0][1][0] = cube[0][2][1];
            temp[0][1][1] = cube[0][1][1];
            temp[0][1][2] = cube[0][0][1];
            temp[0][2][0] = cube[0][2][2];
            temp[0][2][1] = cube[0][1][2];
            temp[0][2][2] = cube[0][0][2];
            temp[2][0][0] = cube[5][0][0];
            temp[2][0][1] = cube[5][0][1];
            temp[2][0][2] = cube[5][0][2];
            temp[3][0][0] = cube[4][0][0];
            temp[3][0][1] = cube[4][0][1];
            temp[3][0][2] = cube[4][0][2];
            temp[4][0][0] = cube[2][0][0];
            temp[4][0][1] = cube[2][0][1];
            temp[4][0][2] = cube[2][0][2];
            temp[5][0][0] = cube[3][0][0];
            temp[5][0][1] = cube[3][0][1];
            temp[5][0][2] = cube[3][0][2];
        }
        // 완료
        else if(input[1] == '-') {
            temp[0][0][0] = cube[0][0][2];
            temp[0][0][1] = cube[0][1][2];
            temp[0][0][2] = cube[0][2][2];
            temp[0][1][0] = cube[0][0][1];
            temp[0][1][1] = cube[0][1][1];
            temp[0][1][2] = cube[0][2][1];
            temp[0][2][0] = cube[0][0][0];
            temp[0][2][1] = cube[0][1][0];
            temp[0][2][2] = cube[0][2][0];
            temp[2][0][0] = cube[4][0][0];
            temp[2][0][1] = cube[4][0][1];
            temp[2][0][2] = cube[4][0][2];
            temp[3][0][0] = cube[5][0][0];
            temp[3][0][1] = cube[5][0][1];
            temp[3][0][2] = cube[5][0][2];
            temp[4][0][0] = cube[3][0][0];
            temp[4][0][1] = cube[3][0][1];
            temp[4][0][2] = cube[3][0][2];
            temp[5][0][0] = cube[2][0][0];
            temp[5][0][1] = cube[2][0][1];
            temp[5][0][2] = cube[2][0][2];
        }
    }
    else if(input[0] == 'D') {
        // 완료
        if(input[1] == '+') {
            temp[1][0][0] = cube[1][2][0];
            temp[1][0][1] = cube[1][1][0];
            temp[1][0][2] = cube[1][0][0];
            temp[1][1][0] = cube[1][2][1];
            temp[1][1][1] = cube[1][1][1];
            temp[1][1][2] = cube[1][0][1];
            temp[1][2][0] = cube[1][2][2];
            temp[1][2][1] = cube[1][1][2];
            temp[1][2][2] = cube[1][0][2];
            temp[2][2][0] = cube[4][2][0];
            temp[2][2][1] = cube[4][2][1];
            temp[2][2][2] = cube[4][2][2];
            temp[3][2][0] = cube[5][2][0];
            temp[3][2][1] = cube[5][2][1];
            temp[3][2][2] = cube[5][2][2];
            temp[4][2][0] = cube[3][2][0];
            temp[4][2][1] = cube[3][2][1];
            temp[4][2][2] = cube[3][2][2];
            temp[5][2][0] = cube[2][2][0];
            temp[5][2][1] = cube[2][2][1];
            temp[5][2][2] = cube[2][2][2];
        }
        // 완료
        else if(input[1] == '-') {
            temp[1][0][0] = cube[1][0][2];
            temp[1][0][1] = cube[1][1][2];
            temp[1][0][2] = cube[1][2][2];
            temp[1][1][0] = cube[1][0][1];
            temp[1][1][1] = cube[1][1][1];
            temp[1][1][2] = cube[1][2][1];
            temp[1][2][0] = cube[1][0][0];
            temp[1][2][1] = cube[1][1][0];
            temp[1][2][2] = cube[1][2][0];
            temp[2][2][0] = cube[5][2][0];
            temp[2][2][1] = cube[5][2][1];
            temp[2][2][2] = cube[5][2][2];
            temp[3][2][0] = cube[4][2][0];
            temp[3][2][1] = cube[4][2][1];
            temp[3][2][2] = cube[4][2][2];
            temp[4][2][0] = cube[2][2][0];
            temp[4][2][1] = cube[2][2][1];
            temp[4][2][2] = cube[2][2][2];
            temp[5][2][0] = cube[3][2][0];
            temp[5][2][1] = cube[3][2][1];
            temp[5][2][2] = cube[3][2][2];            
        }
    }
    else if(input[0] == 'F') {
        // 완료
        if(input[1] == '+') {
            temp[2][0][0] = cube[2][2][0];
            temp[2][0][1] = cube[2][1][0];
            temp[2][0][2] = cube[2][0][0];
            temp[2][1][0] = cube[2][2][1];
            temp[2][1][1] = cube[2][1][1];
            temp[2][1][2] = cube[2][0][1];
            temp[2][2][0] = cube[2][2][2];
            temp[2][2][1] = cube[2][1][2];
            temp[2][2][2] = cube[2][0][2];
            temp[0][2][0] = cube[4][2][2];
            temp[0][2][1] = cube[4][1][2];
            temp[0][2][2] = cube[4][0][2];
            temp[1][0][0] = cube[5][2][0];
            temp[1][0][1] = cube[5][1][0];
            temp[1][0][2] = cube[5][0][0];
            temp[4][0][2] = cube[1][0][0];
            temp[4][1][2] = cube[1][0][1];
            temp[4][2][2] = cube[1][0][2];
            temp[5][0][0] = cube[0][2][0];
            temp[5][1][0] = cube[0][2][1];
            temp[5][2][0] = cube[0][2][2];
        }
        // 완료
        else if(input[1] == '-') {
            temp[2][0][0] = cube[2][0][2];
            temp[2][0][1] = cube[2][1][2];
            temp[2][0][2] = cube[2][2][2];
            temp[2][1][0] = cube[2][0][1];
            temp[2][1][1] = cube[2][1][1];
            temp[2][1][2] = cube[2][2][1];
            temp[2][2][0] = cube[2][0][0];
            temp[2][2][1] = cube[2][1][0];
            temp[2][2][2] = cube[2][2][0];
            temp[0][2][0] = cube[5][0][0];
            temp[0][2][1] = cube[5][1][0];
            temp[0][2][2] = cube[5][2][0];
            temp[1][0][0] = cube[4][0][2];
            temp[1][0][1] = cube[4][1][2];
            temp[1][0][2] = cube[4][2][2];
            temp[4][0][2] = cube[0][2][2];
            temp[4][1][2] = cube[0][2][1];
            temp[4][2][2] = cube[0][2][0];
            temp[5][0][0] = cube[1][0][2];
            temp[5][1][0] = cube[1][0][1];
            temp[5][2][0] = cube[1][0][0];            
        }
    }
    else if(input[0] == 'B') {
        // 완료
        if(input[1] == '+') {
            temp[3][0][0] = cube[3][2][0];
            temp[3][0][1] = cube[3][1][0];
            temp[3][0][2] = cube[3][0][0];
            temp[3][1][0] = cube[3][2][1];
            temp[3][1][1] = cube[3][1][1];
            temp[3][1][2] = cube[3][0][1];
            temp[3][2][0] = cube[3][2][2];
            temp[3][2][1] = cube[3][1][2];
            temp[3][2][2] = cube[3][0][2];
            temp[0][0][0] = cube[5][0][2];
            temp[0][0][1] = cube[5][1][2];
            temp[0][0][2] = cube[5][2][2];
            temp[1][2][0] = cube[4][0][0];
            temp[1][2][1] = cube[4][1][0];
            temp[1][2][2] = cube[4][2][0];
            temp[4][0][0] = cube[0][0][2];
            temp[4][1][0] = cube[0][0][1];
            temp[4][2][0] = cube[0][0][0];
            temp[5][0][2] = cube[1][2][2];
            temp[5][1][2] = cube[1][2][1];
            temp[5][2][2] = cube[1][2][0];
        }
        // 완료
        else if(input[1] == '-') {
            temp[3][0][0] = cube[3][0][2];
            temp[3][0][1] = cube[3][1][2];
            temp[3][0][2] = cube[3][2][2];
            temp[3][1][0] = cube[3][0][1];
            temp[3][1][1] = cube[3][1][1];
            temp[3][1][2] = cube[3][2][1];
            temp[3][2][0] = cube[3][0][0];
            temp[3][2][1] = cube[3][1][0];
            temp[3][2][2] = cube[3][2][0];
            temp[0][0][0] = cube[4][2][0];
            temp[0][0][1] = cube[4][1][0];
            temp[0][0][2] = cube[4][0][0];
            temp[1][2][0] = cube[5][2][2];
            temp[1][2][1] = cube[5][1][2];
            temp[1][2][2] = cube[5][0][2];
            temp[4][0][0] = cube[1][2][0];
            temp[4][1][0] = cube[1][2][1];
            temp[4][2][0] = cube[1][2][2];
            temp[5][0][2] = cube[0][0][0];
            temp[5][1][2] = cube[0][0][1];
            temp[5][2][2] = cube[0][0][2];            
        }
    }
    else if(input[0] == 'L') {
        // 완료
        if(input[1] == '+') {
            temp[4][0][0] = cube[4][2][0];
            temp[4][0][1] = cube[4][1][0];
            temp[4][0][2] = cube[4][0][0];
            temp[4][1][0] = cube[4][2][1];
            temp[4][1][1] = cube[4][1][1];
            temp[4][1][2] = cube[4][0][1];
            temp[4][2][0] = cube[4][2][2];
            temp[4][2][1] = cube[4][1][2];
            temp[4][2][2] = cube[4][0][2];
            temp[0][0][0] = cube[3][2][2];
            temp[0][1][0] = cube[3][1][2];
            temp[0][2][0] = cube[3][0][2];
            temp[1][0][0] = cube[2][0][0];
            temp[1][1][0] = cube[2][1][0];
            temp[1][2][0] = cube[2][2][0];
            temp[2][0][0] = cube[0][0][0];
            temp[2][1][0] = cube[0][1][0];
            temp[2][2][0] = cube[0][2][0];
            temp[3][0][2] = cube[1][2][0];
            temp[3][1][2] = cube[1][1][0];
            temp[3][2][2] = cube[1][0][0];
        }
        // 완료
        else if(input[1] == '-') {
            temp[4][0][0] = cube[4][0][2];
            temp[4][0][1] = cube[4][1][2];
            temp[4][0][2] = cube[4][2][2];
            temp[4][1][0] = cube[4][0][1];
            temp[4][1][1] = cube[4][1][1];
            temp[4][1][2] = cube[4][2][1];
            temp[4][2][0] = cube[4][0][0];
            temp[4][2][1] = cube[4][1][0];
            temp[4][2][2] = cube[4][2][0];
            temp[0][0][0] = cube[2][0][0];
            temp[0][1][0] = cube[2][1][0];
            temp[0][2][0] = cube[2][2][0];
            temp[1][0][0] = cube[3][2][2];
            temp[1][1][0] = cube[3][1][2];
            temp[1][2][0] = cube[3][0][2];
            temp[2][0][0] = cube[1][0][0];
            temp[2][1][0] = cube[1][1][0];
            temp[2][2][0] = cube[1][2][0];
            temp[3][0][2] = cube[0][2][0];
            temp[3][1][2] = cube[0][1][0];
            temp[3][2][2] = cube[0][0][0];
        }
    }
    else if(input[0] == 'R') {
        // 완료
        if(input[1] == '+') {
            temp[5][0][0] = cube[5][2][0];
            temp[5][0][1] = cube[5][1][0];
            temp[5][0][2] = cube[5][0][0];
            temp[5][1][0] = cube[5][2][1];
            temp[5][1][1] = cube[5][1][1];
            temp[5][1][2] = cube[5][0][1];
            temp[5][2][0] = cube[5][2][2];
            temp[5][2][1] = cube[5][1][2];
            temp[5][2][2] = cube[5][0][2];
            temp[0][0][2] = cube[2][0][2];
            temp[0][1][2] = cube[2][1][2];
            temp[0][2][2] = cube[2][2][2];
            temp[1][0][2] = cube[3][2][0];
            temp[1][1][2] = cube[3][1][0];
            temp[1][2][2] = cube[3][0][0];
            temp[2][0][2] = cube[1][0][2];
            temp[2][1][2] = cube[1][1][2];
            temp[2][2][2] = cube[1][2][2];
            temp[3][0][0] = cube[0][2][2];
            temp[3][1][0] = cube[0][1][2];
            temp[3][2][0] = cube[0][0][2];
        }
        // 완료
        else if(input[1] == '-') {
            temp[5][0][0] = cube[5][0][2];
            temp[5][0][1] = cube[5][1][2];
            temp[5][0][2] = cube[5][2][2];
            temp[5][1][0] = cube[5][0][1];
            temp[5][1][1] = cube[5][1][1];
            temp[5][1][2] = cube[5][2][1];
            temp[5][2][0] = cube[5][0][0];
            temp[5][2][1] = cube[5][1][0];
            temp[5][2][2] = cube[5][2][0];
            temp[0][0][2] = cube[3][2][0];
            temp[0][1][2] = cube[3][1][0];
            temp[0][2][2] = cube[3][0][0];
            temp[1][0][2] = cube[2][0][2];
            temp[1][1][2] = cube[2][1][2];
            temp[1][2][2] = cube[2][2][2];
            temp[2][0][2] = cube[0][0][2];
            temp[2][1][2] = cube[0][1][2];
            temp[2][2][2] = cube[0][2][2];
            temp[3][0][0] = cube[1][2][2];
            temp[3][1][0] = cube[1][1][2];
            temp[3][2][0] = cube[1][0][2];
        }
    }

    // 움직인 큐브가 temp에 저장되어 있으므로 이를 다시 cube로 돌림
    copy(&temp[0][0][0], &temp[0][0][0] + sizeof(temp), &cube[0][0][0]);
}

void topColor() {
    for(int i = 0; i < 3; i ++) {
        for(int j = 0; j < 3; j++) {
            cout << cube[0][i][j];
        }
        cout << endl;
    }
}

• 문제 출처 : https://www.acmicpc.net/problem/5373
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.