[5373번] 큐빙(2018년도 삼성 기출 문제)

문제

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

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

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

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

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

 

해당 문제는 작년 삼성 역량테스트 기출문제이다.

 

문제접근법.

 

1. 큐브를 회전하는데 특별한 알고리즘이 존재하지 않는다, 큐브와 맞닿은 면들을 파악해서 회전을 고려하면 된다.

2. 시계 방향과 반 방향이 있는데, 시계 방향으로 3번 돌리면, 반 방향 1번과 같다.

 

코드를 쉽게 짜기 위해서, 큐브의 전개도를 배열을 이용해서 표현한다. 다음은 [7][4][4] 크기의 배열이다. 인덱스를 1부터 사용하기 위해서 [6][3][3]이 아닌, [7][4][4]를 사용한다.

 

 

      123

      456

      789

123 123 123 123

456 456 456 456

789 789 789 789

      123

      456

      789

 

 

다음과 같이 전개도가 있다고 하면, 특정 면을 시계 방향으로 돌리는 건 어떤 면을 돌리는 동일하다.

 

 

123          741

456   =>   852

789          963

 

 

위와 같은데, 중요한 것은 특정 면을 시계 방향으로 돌렸을 때 주위에 있는 면들을 파악해야 한다.

 

앞면을 돌리는 것은 다음과 같다.

 

 

  789             963

3 123 1        1 741 7 

6 456 4   => 2 852 8

9 789 7        3 963 9

   123             741

 

 

나머지 5면에 대해서도 맞닿는 면들의 변화하는 값들을 파악해서 변경해준다. 쉽게 하기 위해서, 큐브의 모든 값들을 TEMP 배열을 통해서 저장을 해두고, 값을 가져다 쓰는 것이 편할 것이다. 구현하기에 까다롭지도 않고, 공간적 감각만 있으면 어느정도 코드를 작성할 수 있다.

 

 

해설코드(C++).

#include <iostream>
#include <cstring>
using namespace std;
 
char cube[7][4][4];
char init[7] = { '.', 'w','y','r', 'o', 'g', 'b' };
int T, N;
char c1, c2;
 
void func(char meon, char bang) {
    int time = 1;
    if (bang == '-') {
        time = 3;
    }
 
    for (int i = 1; i <= time; i++) {
        int temp[7][4][4];
        int idx = 1;
        int cha_row, cha_col;
 
        //copy
        for (int c = 1; c < 7; c++) {
            for (int i = 1; i <= 3; i++) {
                for (int j = 1; j <= 3; j++) {
                    temp[c][i][j] = cube[c][i][j];
                }
            }
        }
 
        if (meon == 'U') {
            idx = 1;
        }
        else if (meon == 'D') {
            idx = 2;
        }
        else if (meon == 'F') {
            idx = 3;
        }
        else if (meon == 'B') {
            idx = 4;
        }
        else if (meon == 'L') {
            idx = 5;
        }
        else if (meon == 'R') {
            idx = 6;
        }
 
        // MEON ROTATE
        cube[idx][1][3] = temp[idx][1][1];
        cube[idx][2][3] = temp[idx][1][2];
        cube[idx][3][3] = temp[idx][1][3];
        cube[idx][1][2] = temp[idx][2][1];
        cube[idx][2][2] = temp[idx][2][2];
        cube[idx][3][2] = temp[idx][2][3];
        cube[idx][1][1] = temp[idx][3][1];
        cube[idx][2][1] = temp[idx][3][2];
        cube[idx][3][1] = temp[idx][3][3];
 
        // ROTATE ORDER
        if (meon == 'U') {
            cube[4][1][3] = temp[5][1][3];
            cube[4][1][2] = temp[5][1][2];
            cube[4][1][1] = temp[5][1][1];
 
            cube[6][1][3] = temp[4][1][3];
            cube[6][1][2] = temp[4][1][2];
            cube[6][1][1] = temp[4][1][1];
 
            cube[3][1][3] = temp[6][1][3];
            cube[3][1][2] = temp[6][1][2];
            cube[3][1][1] = temp[6][1][1];
 
 
            cube[5][1][3] = temp[3][1][3];
            cube[5][1][2] = temp[3][1][2];
            cube[5][1][1] = temp[3][1][1];
        }
        else if (meon == 'D') {
            cube[3][3][1] = temp[5][3][1];
            cube[3][3][2] = temp[5][3][2];
            cube[3][3][3] = temp[5][3][3];
 
            cube[6][3][3] = temp[3][3][3];
            cube[6][3][2] = temp[3][3][2];
            cube[6][3][1] = temp[3][3][1];
 
            cube[4][3][3] = temp[6][3][3];
            cube[4][3][2] = temp[6][3][2];
            cube[4][3][1] = temp[6][3][1];
 
            cube[5][3][3] = temp[4][3][3];
            cube[5][3][2] = temp[4][3][2];
            cube[5][3][1] = temp[4][3][1];
        }
        else if (meon == 'F') {
            cube[1][3][1] = temp[5][3][3];
            cube[1][3][2] = temp[5][2][3]; 
            cube[1][3][3] = temp[5][1][3];
 
            cube[6][1][1] = temp[1][3][1];
            cube[6][2][1] = temp[1][3][2];
            cube[6][3][1] = temp[1][3][3];
 
            cube[2][1][1] = temp[6][3][1];
            cube[2][1][2] = temp[6][2][1];
            cube[2][1][3] = temp[6][1][1];
 
            cube[5][1][3] = temp[2][1][1];
            cube[5][2][3] = temp[2][1][2];
            cube[5][3][3] = temp[2][1][3];
        }                    
        else if (meon == 'B') {
            cube[1][1][3] = temp[6][3][3];
            cube[1][1][2] = temp[6][2][3];
            cube[1][1][1] = temp[6][1][3];
 
            cube[5][1][1] = temp[1][1][3];
            cube[5][2][1] = temp[1][1][2];
            cube[5][3][1] = temp[1][1][1];
 
            cube[2][3][3] = temp[5][3][1];
            cube[2][3][2] = temp[5][2][1];
            cube[2][3][1] = temp[5][1][1];
 
            cube[6][1][3] = temp[2][3][3];
            cube[6][2][3] = temp[2][3][2];
            cube[6][3][3] = temp[2][3][1];
        }
        else if (meon == 'L') {
            cube[1][1][1] = temp[4][3][3];
            cube[1][2][1] = temp[4][2][3];
            cube[1][3][1] = temp[4][1][3];
 
            cube[3][1][1] = temp[1][1][1];
            cube[3][2][1] = temp[1][2][1];
            cube[3][3][1] = temp[1][3][1];
 
            cube[2][1][1] = temp[3][1][1];
            cube[2][2][1] = temp[3][2][1];
            cube[2][3][1] = temp[3][3][1];
 
            cube[4][3][3] = temp[2][1][1];
            cube[4][2][3] = temp[2][2][1];
            cube[4][1][3] = temp[2][3][1];
        }
        else if (meon == 'R') {
            cube[1][1][3] = temp[3][1][3];
            cube[1][2][3] = temp[3][2][3];
            cube[1][3][3] = temp[3][3][3];
 
            cube[4][1][1] = temp[1][3][3];
            cube[4][2][1] = temp[1][2][3];
            cube[4][3][1] = temp[1][1][3];
 
            cube[2][1][3] = temp[4][3][1];
            cube[2][2][3] = temp[4][2][1];
            cube[2][3][3] = temp[4][1][1];
 
            cube[3][1][3] = temp[2][1][3];
            cube[3][2][3] = temp[2][2][3];
            cube[3][3][3] = temp[2][3][3];
        }
    }
}
 
int main(void) {
    //freopen("input.txt", "r", stdin);
    cin >> T;
    for (int t = 1; t <= T; t++) {
        // 1 UP: WHITE
        // 2 DOWN : YELLOW
        // 3 FRONT : RED
        // 4 BACK : ORANGE
        // 5 LEFT : GREEN
        // 6 RIGHT : BLUE
        for (int c = 1; c < 7; c++) {
            for (int i = 1; i <= 3; i++) {
                for (int j = 1; j <= 3; j++) {
                    cube[c][i][j] = init[c];
                }
            }
        }
 
        cin >> N;
        for (int i = 1; i <= N; i++) {
            cin >> c1 >> c2;
            func(c1, c2);
        }
 
        //Answer
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                cout << cube[1][i][j];
            }
            cout << endl;
        }
    }
 
    return 0;
}