[백준-삼성SW역량테스트 기출] 5373번. 큐빙 C++

www.acmicpc.net/problem/5373

5373번: 큐빙

>문제 설명

문제

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

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

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

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

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

입력

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

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

출력

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

 

풀이

엄청난 노가다로 풀 수 있을 것 같았는데, 그럼 실수도 많아질 것 같고 코드가 안이쁠 것 같아서 열심히 고민했다.

전개도로 풀면 풀릴 것 같았는데, 정확한 아이디어가 생각이 안나서 블로그 글을 참고했다.

여기서 전개도에서 각 큐브조각들에 번호를 순서대로 매긴 후 rotation을 해주면 된다는 아이디어를 얻었다!

(반시계방향 회전을 시계방향으로 3번하면 되는 것도!!)

따라서 전개도를 열심히 그려가며 인덱스값을 어떻게 처리해줘야 하는지 계산했다!!

 

우선, 전개도를 그려두고 가운데 면을 시계방향으로 회전해봤다.

회전하기 전

 

회전한 후

회전하면 가운데 면의 번호들은 아래 규칙처럼 바뀐다.

가운데 면의 옆에 붙은 조각들은 

43 44 45   19 22 25   48 47 46    9  6  3
 9  6   3    43 44 45   19 22 25   48 47 46

이렇게 움직인다.

 

 

이걸 처리해주기 위해

• 각 면의 번호들이 담긴 cube 배열
• 각 번호들의 색을 저장하는 cubeColor 배열
• 각 면의 옆쪽 4개의 열의 번호를 저장하는 sideFace 배열

을 만들어 주고, rotation할 때 cube 배열과 sideFace 배열에 담긴 번호들을 이용해서 rotation을 해주었다.

 

코드를 작성할 때 참고하면서 쓴 전개도는 아래에!!

이걸 보면서 옆면들 번호를 적었다..ㅎ

 

옆면 번호는 어느 방향으로 어디부터 적어주는지에 따라 다를 수 있다. index 계산도 달라질 수 있음

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

map<char, int> face = {{'U', 0}, {'D', 1}, {'F', 2}, {'B', 3}, {'L', 4}, {'R', 5}};
map<char, int> count = {{'+', 1}, {'-', 3}};
char color[7] = "wyrogb";
int sideFace[6][12] = {{29,28,27,47,46,45,20,19,18,38,37,36}, //U
                        {24,25,26,51,52,53,33,34,35,42,43,44}, //D
                        {6,7,8,45,48,51,11,10,9,44,41,38}, //F
                        {2,1,0,36,39,42,15,16,17,53,50,47}, //B
                        {0,3,6,18,21,24,9,12,15,35,32,29}, //L
                        {8,5,2,27,30,33,17,14,11,26,23,20} //R 
                        };
                        
int cube[6][3][3]; //save each face's number
char cubeColor[55]; //save each face's color matching number
int T;
int n;

void rotate(int f, int dir){
    
    char temp[3][3];
    int rot[12];
    
    while(dir--){
        
        //turn a face
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                temp[j][2-i] = cubeColor[cube[f][i][j]];
            }
        }
        
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                cubeColor[cube[f][i][j]] = temp[i][j];
            }
        }
        
        //turn side face
        for(int i=0; i<12; i++){
            rot[i] = cubeColor[sideFace[f][i]];
        }
        
        for(int i=0; i<12; i++){
            cubeColor[sideFace[f][i]] = rot[(i+9)%12];
        }
    }
    
}

void initialize(){
    
    //cube initial value
    for(int i=0; i<6; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<3; k++){
                cube[i][j][k] = i*9+j*3+k;
            }
        }
    }
    
}

int main()
{
    cin>>T;
    
    initialize();
    
    for(int i=0; i<T; i++){
        
        cin>>n;
        
        //initialize cube's color
        for(int j=0; j<6; j++){
            for(int k=0; k<9; k++){
                cubeColor[j*9+k] = color[j];
            }
        }
        
        //input rotate information
        //then, rotate
        for(int j=0; j<n; j++){
            string moveTo;
            cin>>moveTo;
            rotate(face[moveTo.at(0)], count[moveTo.at(1)]);
        }
        
        //print upper face
        for(int j=0; j<3; j++){
            for(int k=0; k<3; k++){
                cout<<cubeColor[cube[0][j][k]];
            }
            cout<<"\n";
        }
    }

    return 0;
}