[백준 - 5373] 큐빙 - C++

분류: 시뮬레이션, 좌표계산 /

 

문제

문제 링크

문제 설명

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

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

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

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

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

입력

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

• 첫째 줄에 큐브를 돌린 횟수 n이 주어진다. (1 ≤ n ≤ 1000)
• 둘째 줄에는 큐브를 돌린 방법이 주어진다. 각 방법은 공백으로 구분되어져 있으며, 첫 번째 문자는 돌린 면이다. U: 윗 면, D: 아랫 면, F: 앞 면, B: 뒷 면, L: 왼쪽 면, R: 오른쪽 면이다. 두 번째 문자는 돌린 방향이다. +인 경우에는 시계 방향 (그 면을 바라봤을 때가 기준), -인 경우에는 반시계 방향이다.

출력

각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란색은 y, 빨간색은 r, 오렌지색은 o, 초록색은 g, 파란색은 b.

 

풀이

#include <iostream>
#include <unordered_map>
using namespace std;
const int FACE_LENGTH = 8, SIDE_LENGTH = 12;

char cube[48];
char color[6] = {'w', 'g', 'r', 'b', 'o', 'y'};
unordered_map<char, int> keyMap = {
    {'U', 0}, {'L', 1}, {'F', 2}, {'R', 3}, {'B', 4}, {'D', 5}
};
int faceIndex[6][FACE_LENGTH] = {
    {0, 1, 2, 3, 4, 5, 6, 7}, // U
    {8, 9, 10, 11, 12, 13, 14, 15}, // L
    {16, 17, 18, 19, 20, 21, 22, 23}, // F
    {24, 25, 26, 27, 28, 29, 30, 31}, // R
    {32, 33, 34, 35, 36, 37, 38, 39}, // B
    {40, 41, 42, 43, 44, 45, 46, 47} // D
};
int sideIndex[6][SIDE_LENGTH] = {
    {34, 33, 32, 26, 25, 24, 18, 17, 16, 10, 9, 8}, // U
    {0, 7, 6, 16, 23, 22, 40, 47, 46, 36, 35, 34}, // L
    {6, 5, 4, 24, 31, 30, 42, 41, 40, 12, 11, 10}, // F
    {4, 3, 2, 32, 39, 38, 44, 43, 42, 20, 19, 18}, // R
    {2, 1, 0, 8, 15, 14, 46, 45, 44, 28, 27, 26}, // B
    {22, 21, 20, 30, 29, 28, 38, 37, 36, 14, 13, 12} // D
};

inline void init() { for(int i=0; i<48; i++) cube[i] = color[i/8]; }

void rotate(int index[], int n, int offset) {
    int tmp[n];
    for(int i = 0, t = offset; i < n; i++) {
        tmp[t++] = cube[index[i]];
        if(t == n) t %= n;
    }
    for(int i=0; i<n; i++) cube[index[i]] = tmp[i];
}

void rotateFace(int face, bool isClockwise) {
    int rot = isClockwise ? 1 : 3;
    rotate(faceIndex[face], FACE_LENGTH, 2*rot);
    rotate(sideIndex[face], SIDE_LENGTH, 3*rot);
}

void printUp() {
    int ln = 0;
    for(int i : {0, 1, 2, 7, -1, 3, 6, 5, 4}) {
        if(i < 0) cout << 'w';
        else cout << cube[i];
        if(++ln % 3 == 0) cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    while(T--) {
        int n; cin >> n;

        init();
        while(n--) {
            char face, sign; cin >> face >> sign;
            rotateFace(keyMap[face], sign == '+');
        }
        printUp();
    }
}

 

처음 봤을 때 어떻게 구현할 지 조금 막막한 했던 문제

 

큐브를 해보면 알겠지만 큐브의 중앙 피스는 고정되어있고 모서리의 조각만 이동한다.

 

움직이는 조각은 모서리 12개, 꼭짓점 8개로 총 20개다.

이를 이용해 2개의 면을 갖는 조각 12개, 3개의 면을 갖는 조각 8개와 각 조각의 `(pitch, roll, yaw)`를 이용해 구현하는 것이 뭔가 진짜 게임만드는 사람들이 구현하는 방법일 것 같지만 이는 나중에 해보기로하고 바로 구현할 수 있는 더 쉬운 방법으로 구현했다.

 

조각 단위가 아닌 스티커 단위로 구현했다.

큐브에는 총 54개의 스티커가 붙어있고 각 면의 중앙을 제외하면 움직이는 스티커는 48개다.

3차원으로 구현할 수도 있지만(`cube[6][3][3]`) 좌표계산이 더 복잡할 것 같아서 1차원으로 구현했다.(`cube[48]`)

48개의 스티커에 번호를 부여해 6개의 면이 각각 회전할 때 함께 움직이는 스티커를 번호로 그루핑해준다.

(`faceIndex[6][8]`, `sideIndex[6][12]`)

부여된 번호를 큐브의 전개도와 함께 보면 아래와 같다. 시계방향으로 회전시키므로 숫자는 시계방향으로 넘버링한다.

/*
          0  1  2        
          7  U  3        
          6  5  4
8  9  10  16 17 18  24 25 26  32 33 34
15 L  11  23 F  19  31 R  27  39 B  35
14 13 12  22 21 20  30 29 28  38 37 36
          40 41 42
          47 D  43
          46 45 44
*/

`faceIndex[][]`는 바라보는 면의 중앙을 제외한 8개 스티커의 번호다.

`sideIndex[][]`는 바라보는 면의 4개의 옆면에서 바라보는 면과 인접한 12개 스티커의 번호다.

 

`rotateFace()` 바라보는 면(`face`)와 회전 수(`rot`)로 `faceIndex[face][8]`과 `sideIndex[face][12]`를 회전시킨다.

반시계방향은 시계방향으로 3번 돌린 것과 같다.(`rot = isClockwise ? 1 : 3`)

`faceIndex[][8]`은 1차원 배열에서 2칸을 이동해야 90도 회전한 것이므로 `rot` 회전은 `2 * rot`만큼 이동시킨 것이다.

`sideIndex[][12]`는 1차원 배열에서 3칸을 이동해야 90되 회전한 것이므로 `rot` 회전은 `3 * rot`만큼 이동시킨 것이다.

 

`rotate()`는 1차원 배열을 `logical circular array`로 하여 `offset`칸 만큼 이동(회전)시키는 함수다.

`tmp[]`를 만들고 `offset`만큼 차이나게 원본을 밀어 저장하여 배열을 원형 회전 시키는 방법은 코딩테스트를 보다가 생각한 방법이다. 해당 코딩테스트의 문제에는 2차원 정사각형의 숫자를 시계방향 혹은 반 시계방향으로 회전 시키는 것을 구현하는 부분이 있었는데 부분적으로 복기해보면 아래와 같다.

/*
변의 길이가 5인 정사각형 시계방향 2칸 회전
변의 길이가 3인 정사각형 반시계방향 1칸 회전

A B C D E       K F A B C
F G H I J       P H I N D
K L M N O  -->  U G M S E
P Q R S T       V L Q R J
U V W X Y       W X Y T O
*/

string board[5] = {"ABCDE", "FGHIJ", "KLMNO", "PQRST", "UVWXY"};
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void rotate(int startX, int startY, int n, int offset) {
    int size = 4 * (n - 1);
    char tmp[size];
    if(offset < 0) offset += size;
    else if(offset > size) offset %= size;

    int dir = 0, x = startX, y = startY;
    for(int i = 0; i < size; i++) {
        tmp[(offset + i) % size] = board[x][y];
        if(i % (n-1) == 0) dir = (dir + 1) % 4;
        x += dx[dir];
        y += dy[dir];
    }
    // dir = 0; x = startX; y = startY;
    for(int i = 0; i < size; i++) {
        board[x][y] = tmp[i];
        if(i % (n-1) == 0) dir = (dir + 1) % 4;
        x += dx[dir];
        y += dy[dir];
    }
}

void print() { for(int i=0; i<5; i++) cout << board[i] << '\n'; }
int main() {
    print();

    rotate(0, 0, 5, 2); // 변의 길이가 5인 정사각형 시계방향 2칸 회전
    rotate(1, 1, 3, -1); // 변의 길이가 3인 정사각형 반시계방향 1칸 회전
    
    cout << '\n';
    print();
}