[삼성 기출 문제] 백준 5373 큐빙

문제 링크

어떻게 풀까?

진정한 시뮬레이션입니다.

정말... 말 그대로 3x3x3 큐브의 U D F B L R을 시계방향과 반시계방향으로 돌리는 것을 구현하면 됩니다!

-끝- 

이라고 하기엔 너무 힘들고 가혹한 시뮬레이션 입니다.

사람에 따라서는 코드 길이도 200~300줄까지 될겁니다.

if문과 else문으로 떡칠이 되어있기 때문이죠!

아는 분의 협조를 구해서 가져온 코드의 일부분 입니다!

            if (s == "U+") {
                Up_cw(a);
            }
            else if (s == "U-") {
                Up_cw(a); Up_cw(a); Up_cw(a);
            }
            else if (s == "D+") {
                Down_cw(a);
            }
            else if (s == "D-") {
                Down_cw(a); Down_cw(a); Down_cw(a);
            }
            else if (s == "F+") {
                Forward_cw(a);
            }
            else if (s == "F-") {
                Forward_cw(a); Forward_cw(a); Forward_cw(a);
            }
            else if (s == "B+") {
                Backward_cw(a);
            }
            else if (s == "B-") {
                Backward_cw(a); Backward_cw(a); Backward_cw(a);
            }
            else if (s == "L+") {
                Left_cw(a);
            }
            else if (s == "L-") {
                Left_cw(a); Left_cw(a); Left_cw(a);
            }
            else if (s == "R+") {
                Right_cw(a);
            }
            else if (s == "R-") {
                Right_cw(a); Right_cw(a); Right_cw(a);
            }

else if 만으로도 굉장히 엄청나게 많습니다..

cw들 중 하나인 Up_cw는 어떨까요?

 

void Up_cw(vector<vector<vector<char> > > &a) {
    cw(a[0]); cw(a[0]); //cw(a[0]);
    vector<vector<char> > temp = a[1];
    //1<-2<-3<-4<-1
    a[1][0][0] = a[2][2][0];
    a[1][0][1] = a[2][1][0];
    a[1][0][2] = a[2][0][0];
 
    a[2][2][0] = a[3][2][2];
    a[2][1][0] = a[3][2][1];
    a[2][0][0] = a[3][2][0];
 
    a[3][2][2] = a[4][0][2];
    a[3][2][1] = a[4][1][2];
    a[3][2][0] = a[4][2][2];
 
    a[4][0][2] = temp[0][0];
    a[4][1][2] = temp[0][1];
    a[4][2][2] = temp[0][2];
}

이 함수들을 모두 만들려면.. 엄청난 시간이 필요하겠죠?

디버깅도 말도 안되게 힘들 것입니다.

자! 그렇다면 제가 하는 방법을 소개해드리겠습니다.

정말 머리를 쥐어뜯어서 어떻게하면 줄일 수 있을까 고심한 결과로 나왔습니다!!

먼저 함수의 개수를 12개에서 6개로 줄여봅시다.

이전에 백준님이 큐빙문제풀이를 실시간 스트리밍으로 강의한 적이 있으십니다.

그때 하신 명언이 있죠.

'반시계 방향은 시계 방향을 3번 돌리면 된다.'

생각해보면, 해당 문제는 돌릴때마다 시간복잡도가 굉장히 작습니다.

따라서, 3배로 돌린다고 해서 시간초과할 이유는 없는것이죠!

원래 각각의 면 6개를 반시계, 시계방향으로 돌려야해서 12개의 함수였지만..

일단 이렇게 절반이 줄었습니다.

단순 시뮬레이션 문제는 보통 시간 초과의 문제는 걱정할 필요는 없기 때문에 

최대한! 구현이 간편한 쪽으로 방향을 잡는 것이 좋습니다.

저도 시계 방향으로 돌리는 것을 기준으로 삼겠습니다. 

그렇게 하면 '+'는 1로 '-'는 3으로 카운트를 잡는 것이 필요하겠죠.

이제 F+는 앞면을 시계 방향으로 한 번돌리고, F-는 앞면을 시계 방향으로 3번 돌린다는 의미가 되었습니다.

이제 나머지는 진짜로 어떻게 돌리면 될지 구현하는 것 입니다.

이 방법을 알기 위해선 테이블을 만드는 법에 대해서 알아두는게 좋습니다.

테이블 만들기에 대해 관심이 있으시면 이 글을 한번 봐주세요.

자 그럼! 큐빙에서는 테이블을 어떻게 만드는게 좋을까요?

우선.. 돌리는 행위를 봅시다. 전개도를 보면 쉽게 알 수 있습니다.

자! 여러분을 위해서 전개도를 가져왔습니다. 무려 색도 칠했습니다.

한번 F+를 해볼까요??

이렇게 변하는군요!

차이점을 아시겠나요!?

그림을 자세히 보시면 달라지는 부분은아래 그림과 같습니다.

기존

돌린 후

면마다 돌리면 달라지는 배열은 총 21개입니다!

바로, 돌아가는 면 9개와 9개의 면에 달린 또다른 면들 12개이죠.

일단, 면이 돌아가는 지점 9개는 행이 열의 끝에서 부터 다시 채워지고, 열이 처음부터 다시 커진다는 점을 이용할 수 있습니다.

(자세한건 뒤에 코드를 보시면 됩니다.)

문제는 옆에 접하는 면들 12군데죠. (6,7,8,51,48,45, ...)

해당 부분들이 바로 면을 돌릴때 달라져야하는 데이터들 입니다.

그리고 시계 방향의 회전은 기존에 있던 수를 그대로 옆으로 밀어내는 방법을 사용합니다.

큐브의 경우는 기존의 수를 3칸 밀어넣는 방법으로 시계 방향으로의 회전을 구현할 수 있습니다!!

     6   ,7  ,8   ,44 ,41 ,38 ,11 ,10  ,9  ,45 ,48 ,51

=> 44 ,41 ,38 ,11 ,10 ,9   ,45 ,48 ,51 ,6   ,7   ,8

기존과 비교하면 딱 맞죠!?

이제 시계방향의 함수를

[면][12개의 면 데이터]의 테이블만 만들어 놓으면 면에 따라서 큐를 이용해서 데이터를 밀 수 있을 겁니다.

이제 F 라는 문자열이 들어오면, rot[2]의 배열가도록만 처리하면 되겠네요! 

이때도 int conv['F'] = 2 이런식으로 char를 int형으로 변환하는 또 다른 테이블을 만들어서 들어오는 명령어를 손쉽게 int 형으로 변환할 수 있습니다!

그럼 회전하는 코드와 데이터를 볼까요!?

enum FACE{U,D,F,B,L,R,SIZE};
char arr[55];
int cube[SIZE][3][3];
char temp[3][3];
 
int rot[6][12] = {
    {36,37,38,18,19,20,45,46,47,27,28,29},        //U
    {33,34,35,51,52,53,24,25,26,42,43,44},        //D
    {6,7,8,44,41,38,11,10,9,45,48,51},            //F
    {2,1,0,53,50,47,15,16,17,36,39,42},            //B
    {0,3,6,35,32,29,9,12,15,18,21,24},            //L
    {8,5,2,26,23,20,17,14,11,27,30,33}            //R
};
 
void rotate(FACE f,int cnt){
    char que[12];
    
    while (cnt--) {
        //큐에 데이터를 넣습니다.
        for (int i = 0; i < 12; i++) {
            que[i] = arr[rot[f][i]];
        }
 
        //큐를 3칸 밀어서 넣습니다.
        for (int i = 0; i < 12; i++) {
            arr[rot[f][i]]= que[(i + 3) % 12];
        }
 
        //면을 돌립니다.
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
            temp[j][2-i] = arr[cube[f][i][j]];
        }
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) arr[cube[f][i][j]] = temp[i][j];
    }
}

심플하죠!?

해당 부분만 있으면 12개의 명령어에 대해 모든 돌리기 처리를 할 수 있습니다.

참고로, 테이블을 만들 때 전개도를 주석으로 처리해 놓으면 그나마 쉽게 테이블을 작성할 수 있답니다.

구글을 돌아다니다가 어떤 분이 이렇게 전개도를 그리신 코드를 찾았습니다. 

굉장히 현명하신 분이라고 생각합니다.

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

코드

#include<cstdio>
 
/*            U
          0  1  2
          3  4  5
          6  7  8
L        __________    R            B
36 37 38|F18 19 20 | 45 46 47 | 27 28 29
39 40 41| 21 22 23 | 48 49 50 | 30 31 32
42 43 44| 24 25 26 | 51 52 53 | 33 34 35
        -----------
          9  10 11
          12 13 14
          15 16 17
          D
*/ 
enum FACE{U,D,F,B,L,R,SIZE};
char init[7] = "wyrogb";
char arr[55];
int cube[SIZE][3][3];
char temp[3][3];
 
int rot[6][12] = {
    {36,37,38,18,19,20,45,46,47,27,28,29},        //U
    {33,34,35,51,52,53,24,25,26,42,43,44},        //D
    {6,7,8,44,41,38,11,10,9,45,48,51},            //F
    {2,1,0,53,50,47,15,16,17,36,39,42},            //B
    {0,3,6,35,32,29,9,12,15,18,21,24},            //L
    {8,5,2,26,23,20,17,14,11,27,30,33}            //R
};
 
void rotate(FACE f,int cnt){
    char que[12];
    
    while (cnt--) {
        for (int i = 0; i < 12; i++) {
            que[i] = arr[rot[f][i]];
        }
        for (int i = 0; i < 12; i++) {
            arr[rot[f][i]]= que[(i + 3) % 12];
        }
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
            temp[j][2-i] = arr[cube[f][i][j]];
        }
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) arr[cube[f][i][j]] = temp[i][j];
    }
}
 
int conv[256];
 
int main() {
    conv['-'] = 3;
    conv['+'] = 1;
    conv['U'] = U;
    conv['D'] = D;
    conv['F'] = F;
    conv['B'] = B;
    conv['L'] = L;
    conv['R'] = R;
 
    //큐브 인덱스 부여하기
    for (int i = 0; i < SIZE; 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 n, m;
    char comm[3];
 
    scanf("%d\n",&n);
 
    while (n--) {
        //큐브 초기화
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 9; j++) {
                arr[i*9+j] = init[i];
            }
        }
 
        scanf("\n%d\n", &m);
 
        while (m--) {
            scanf("%s \n", comm);
 
            int f = conv[comm[0]], cnt = conv[comm[1]];
            rotate((FACE)f, cnt);
        }
 
        //출력
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                printf("%c", arr[cube[U][i][j]]);
            }
            printf("\n");
        }
    }
 
    return 0;
}

시간복잡도

시간복잡도는 O(n*m) 입니다.