5373. 큐빙

문제 링크

5373번: 큐빙

 

풀이

문제가 논리적으로 어렵진 않으나, 루빅스 큐브의 회전을 구현하기가 까다로울 수 있다. 일단 각 면이 회전하면서 어느 칸의 색상이 어느 면으로 이동하는지, 그것을 주의깊게 생각해서 구현한다면 어려움은 없다.

 

필자는 구현은 어찌저찌 할 수 있었으나, 최적화에 쓸데없이 많은 시간을 소비했다. 각 면을 회전하는 함수를 좀 더 최적화해서 하나의 함수로 통합해서 나타낼 수 없을지, 그런 고민이다. 결국 하단의 소스코드를 보면 알겠지만 앞뒤/좌우/위아래 회전/시계방향/시계 반대방향 회전 함수 총 5개로 최적화할 수 있었다. 구현 문제는 코드를 개떡같이 짜도 찰떡같이 돌아가면 그만이지만, 아무래도 깔끔하게 정리해서 짜는 걸 선호하는 타입이라...

 

구현할때 주의사항으로 각 면의 인덱스를 어디서부터 (0, 0)으로 정할 것인지 명확히 정해 놓도록 하자. 그래야 회전할 때 칸이 이상하게 바뀌는 참사를 줄일 수 있다.

 

시간 복잡도

테스트케이스의 개수를 \(T\), \(i\)번째 테스트케이스에서 회전 횟수를 \(N_{i}\)라고 하자. 회전 한 번에서 값이 바뀌는 칸의 개수는 21칸(면 하나의 9칸 + 면 하나 주변의 3 × 4 = 12칸)으로 일정하다. 따라서 코드의 시간복잡도에 영항을 끼치는 요소는 \(T\)와 \(N\)뿐이며, 식으로 나타내면 \(O(\sum\limits_{i=1}^T N_{i})\)이다.

 

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#define UP      0
#define DOWN    1
#define FRONT   2
#define BACK    3
#define LEFT    4
#define RIGHT   5
using namespace std;

int T, n;
string str;
char cube[6][3][3];

// 큐브를 초기 상태로 초기화하는 함수
void cube_init() {
    fill(cube[UP][0], cube[UP][0] + 9, 'w');
    fill(cube[DOWN][0], cube[DOWN][0] + 9, 'y');
    fill(cube[FRONT][0], cube[FRONT][0] + 9, 'r');
    fill(cube[BACK][0], cube[BACK][0] + 9, 'o');
    fill(cube[LEFT][0], cube[LEFT][0] + 9, 'g');
    fill(cube[RIGHT][0], cube[RIGHT][0] + 9, 'b');
}

// 시계 방향으로 면을 회전하는 함수
void rotateFaceCW(int face) {
    char tmp[3][3];
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            tmp[i][j] = cube[face][2 - j][i];
        }
    }
    copy(&tmp[0][0], &tmp[0][0] + 9, cube[face][0]);
}

// 반시계 방향으로 면을 회전하는 함수
void rotateFaceCCW(int face) {
    char tmp[3][3];
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            tmp[i][j] = cube[face][j][2 - i];
        }
    }
    copy(&tmp[0][0], &tmp[0][0] + 9, cube[face][0]);
}

int convertFaceChar(char face) {
    switch(face) {
        case 'U': return UP;
        case 'D': return DOWN;
        case 'F': return FRONT;
        case 'B': return BACK;
        case 'L': return LEFT;
        case 'R': return RIGHT;
    }
}

// 위/아래 면을 회전하는 함수
void rotateFaceSideUD(int face, char dir) {
    int r = face == UP ? 0 : 2;
    for(int i = 0; i < 3; i++) {
        swap(cube[LEFT][r][i], cube[FRONT][r][i]);
        swap(cube[RIGHT][r][i], cube[BACK][r][i]);
    }
    
    if((face == UP && dir == '+') || (face == DOWN && dir == '-')) {
        for(int i = 0; i < 3; i++) {
            swap(cube[FRONT][r][i], cube[BACK][r][i]);
        }
    }
    else {
        for(int i = 0; i < 3; i++) {
            swap(cube[LEFT][r][i], cube[RIGHT][r][i]);
        }
    }
}

// 왼쪽/오른쪽 면을 회전하는 함수
void rotateFaceSideLR(int face, char dir) {
    int c = face == LEFT ? 0 : 2;
    for(int i = 0; i < 3; i++) {
        swap(cube[UP][i][c], cube[BACK][2 - i][2 - c]);
        swap(cube[DOWN][i][c], cube[FRONT][i][c]);
    }
    
    if((face == LEFT && dir == '+') || (face == RIGHT && dir == '-')) {
        for(int i = 0; i < 3; i++) {
            swap(cube[FRONT][i][c], cube[BACK][2 - i][2 - c]);
        }
    }
    else {
        for(int i = 0; i < 3; i++) {
            swap(cube[UP][i][c], cube[DOWN][i][c]);
        }
    }
}

// 앞/뒤 면을 회전하는 함수
void rotateFaceSideFB(int face, char dir) {
    int j = face == FRONT ? 0 : 2;
    for(int i = 0; i < 3; i++) {
        swap(cube[UP][2 - j][i], cube[LEFT][2 - i][2 - j]);
        swap(cube[DOWN][j][i], cube[RIGHT][2 - i][j]);
    }
    
    if((face == FRONT && dir == '+') || (face == BACK && dir == '-')) {
        for(int i = 0; i < 3; i++) {
            swap(cube[LEFT][i][2 - j], cube[RIGHT][2 - i][j]);
        }
    }
    else {
        for(int i = 0; i < 3; i++) {
            swap(cube[UP][2 - j][i], cube[DOWN][j][2 - i]);
        }
    }
}

// 주어진 면을 회전하는 함수
void rotate(int face, char dir) {
    if(dir == '+') rotateFaceCW(face);
    else rotateFaceCCW(face);
    
    switch(face) {
        case UP:
        case DOWN:
            rotateFaceSideUD(face, dir);
            break;
        case LEFT:
        case RIGHT:
            rotateFaceSideLR(face, dir);
            break;
        case FRONT:
        case BACK:
            rotateFaceSideFB(face, dir);
            break;
    }
}

void printUpFace() {
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cout << cube[UP][i][j];
        }
        cout << '\n';
    }
}
    
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> T;
    while(T--) {
        cube_init();
        cin >> n;
        while(n--) {
            cin >> str;
            rotate(convertFaceChar(str[0]), str[1]);
        }
        printUpFace();
    }
    
    return 0;
}