BJ5373 큐빙
By TBTB7
SW/알고리즘 문제풀이
2020. 2. 14. 14:48

2020.02.14

큐빙

풀이

알고리즘 : Simulation

box[6] 에 큐브의 6개 면에 대해 char 를 인덱싱 할 수 있도록 써두었다.

color[6]에 큐브 6개의 면을 초기화 할 색깔들을 써두었다.

myCube에 6개의 면(각 면마다 3x3) 의 색들을 담았다.

turnIdx 배열을 통해 6개의 면 중 바라보고 돌릴 면과 이때 바라보는 면을 둘러싸는 4개의 면을 아래,오른쪽,위,왼쪽 순으로 찾을 수 있도록 써두었다.

turnInfo : 6개의 면 중 바라보고 돌릴 면을 정했을 때 turnIdx에서 나온 결과에 따라 해당 index들 중 기준점이 되는 점이 각 경우마다 달라지므로 경우에 맞게 써두었다.

blockIdx : turnInfo에서 받아온 기준점에 따라 다음 두개의 숫자를 가져오는 방식을 써두었다.

resetCube함수 : 큐브를 초기화하는 함수.

doNext함수 : input으로 받은 문자열의 정보에 따라 중심 box를 boxIdx에 담고 인접한 4개의 면에서 해당 boxIdx 면에 닿아있는 3개씩의 값들을 deque에 담는다.

turnCube : deque를 시계/반시계 방향에 따라 돌리고, 바라보고 있는 면도 함께 돌린다.

Simulation 순서와 각 경우에 맞춰서 index을 해주어 모든 경우에 대해 처리할 수 있도록 구현하였다.

Code 1 정답

#include<cstdio>
#include<deque>
using namespace std;

const int MAX = 10;
const char box[6] = { 'U','D','F','B','L','R' };
const char color[6] = { 'w','y','r','o','g','b' };
char myCube[6][3][3];    // 0 : 윗면 1 : 아랫면 2 : 앞면 3 : 뒷면 4 : 왼쪽 5 : 오른쪽
int N, T;
int turnIdx[6][4] = { {2,5,3,4},{3,5,2,4},{1,5,0,4},{1,4,0,5},{1,2,0,3},{1,3,0,2} };
int turnInfo[6][4][2] = { {{0,0},{0,0},{0,0},{0,0}},{{2,2},{2,2},{2,2},{2,2}},{{0,0},{2,0},{2,2},{0,2}},
                        {{2,2},{2,0},{0,0},{0,2}},{{2,0},{2,0},{2,0},{0,2}},{{0,2},{2,0},{0,2},{0,2}} };
int blockIdx[2][2][3][2] = { {{{0,0},{0,1},{0,2}},{{0,2},{1,2},{2,2}}},
                                {{{2,0},{1,0},{0,0}},{{2,2},{2,1},{2,0}}} };
deque <char> myDeq;

void resetCube() {
    for (int d = 0; d < 6; d++) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                myCube[d][i][j] = color[d];
            }
        }
    }
}


void turnCube(int num, char d) {
    char tmpCube[3][3];

    if (d == '+') {
        for (int i = 0; i < 3; i++) {
            char tmp = myDeq.front();
            myDeq.pop_front();
            myDeq.push_back(tmp);
            for (int j = 0; j < 3; j++) {
                tmpCube[i][j] = myCube[num][i][j];
            }
        }
        for (int i = 0; i < 3; i++) myCube[num][i][2] = tmpCube[0][i];
        for (int i = 0; i < 3; i++) myCube[num][i][0] = tmpCube[2][i];
        myCube[num][0][1] = tmpCube[1][0];
        myCube[num][2][1] = tmpCube[1][2];
    }
    else if (d == '-') {
        for (int i = 0; i < 3; i++) {
            char tmp = myDeq.back();
            myDeq.pop_back();
            myDeq.push_front(tmp);
            for (int j = 0; j < 3; j++) {
                tmpCube[i][j] = myCube[num][i][j];
            }
        }
        for (int i = 0; i < 3; i++) myCube[num][2-i][0] = tmpCube[0][i];
        for (int i = 0; i < 3; i++) myCube[num][2-i][2] = tmpCube[2][i];
        myCube[num][0][1] = tmpCube[1][2];
        myCube[num][2][1] = tmpCube[1][0];
    }
}

void doNext(char num,char dir) {
    int boxIdx=-1;
    for (int i = 0; i < 6; i++) {
        if (num == box[i]) {
            boxIdx = i;
            break;
        }
    }

    for(int i=0;i<4;i++){
        int idx = turnIdx[boxIdx][i];
        int r = turnInfo[boxIdx][i][0];
        int c = turnInfo[boxIdx][i][1];
        for (int j = 0; j < 3; j++) {
            int y = blockIdx[r / 2][c / 2][j][0];
            int x = blockIdx[r / 2][c / 2][j][1];
            myDeq.push_back(myCube[idx][y][x]);
        }
    }
    turnCube(boxIdx,dir);

    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int idx = turnIdx[boxIdx][i];
        int r = turnInfo[boxIdx][i][0];
        int c = turnInfo[boxIdx][i][1];
        for (int j = 0; j < 3; j++) {
            int y = blockIdx[r / 2][c / 2][j][0];
            int x = blockIdx[r / 2][c / 2][j][1];
            myCube[idx][y][x] = myDeq[i*3+j];
        }
    }
    deque <char> empty;
    empty.swap(myDeq);
}

int main() {
    scanf("%d", &T);
    for (int tc = 0; tc < T; tc++) {
        scanf("%d", &N);
        resetCube();
        for (int n = 0; n < N; n++) {
            char howToTurn[3];
            scanf("%s", howToTurn);
            doNext(howToTurn[0], howToTurn[1]);
        }
        for(int i=0;i<3;i++){
            for (int j = 0; j < 3; j++) {
                printf("%c", myCube[0][i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

Code2 오답

#include<cstdio>
#include<deque>
using namespace std;

const int MAX = 10;
const char box[6] = { 'U','D','F','B','L','R' };
const char color[6] = { 'w','y','r','o','g','b' };
char myCube[6][3][3];        // 0 : 윗면 1 : 아랫면 2 : 앞면 3 : 뒷면 4 : 왼쪽 5 : 오른쪽
char howToTurn[MAX];
int N,T;
int turnIdx[6][4] = { {2,5,3,4},{3,5,2,4},{1,5,0,4},{0,5,1,4}, {1,2,0,3},{1,3,0,2} };
int turnInfo[6][4][2] = { {{0,0},{0,0},{2,2},{0,0}},{{0,0},{2,2},{2,2},{2,0}},{{0,0},{2,0},{2,2},{0,2}},
                        {{0,0},{0,2},{2,2},{2,0}},{{2,0},{2,0},{2,0},{2,0}},{{0,2},{0,2},{0,2},{0,2}} };
int blockIdx[2][2][3][2] = {{{{0,0},{0,1},{0,2}},{{0,2},{1,2},{2,2}}},
                                {{{2,0},{1,0},{0,0}},{{2,2},{2,1},{2,0}}}};
deque <char> myDeq;

void resetCube() {
    for (int d = 0; d < 6; d++) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                myCube[d][i][j] = color[d];
            }
        }
    }
}


void turnCube(int num, char d) {
    int tmpCube[3][3];

    if (d == '+') {
        for (int i = 0; i < 3; i++) {
            char tmp = myDeq.front();
            myDeq.pop_front();
            myDeq.push_back(tmp);
            for (int j = 0; j < 3; j++) {
                tmpCube[i][j] = myCube[num][i][j];
            }
        }
        for (int i = 0; i < 3; i++) myCube[num][i][2] = tmpCube[0][i];
        for (int i = 0; i < 3; i++) myCube[num][i][0] = tmpCube[2][i];
        myCube[num][0][1] = tmpCube[1][0];
        myCube[num][2][1] = tmpCube[1][2];
    }
    else if (d == '-') {
        for (int i = 0; i < 3; i++) {
            char tmp = myDeq.back();
            myDeq.pop_back();
            myDeq.push_front(tmp);
            for (int j = 0; j < 3; j++) {
                tmpCube[i][j] = myCube[num][i][j];
            }
        }
        for (int i = 0; i < 3; i++) myCube[num][2-i][0] = tmpCube[0][i];
        for (int i = 0; i < 3; i++) myCube[num][2-i][2] = tmpCube[2][i];
        myCube[num][0][1] = tmpCube[1][2];
        myCube[num][2][1] = tmpCube[1][0];
    }
}

void doNext(char num,char dir) {
    int boxIdx=-1;
    for (int i = 0; i < 6; i++) {
        if (num == box[i]) {
            boxIdx = i;
            break;
        }
    }

    for(int i=0;i<4;i++){
        int idx = turnIdx[boxIdx][i];
        int r = turnInfo[boxIdx][i][0];
        int c = turnInfo[boxIdx][i][1];
        for (int j = 0; j < 3; j++) {
            int y = blockIdx[r / 2][c / 2][j][0];
            int x = blockIdx[r / 2][c / 2][j][1];
            myDeq.push_back(myCube[idx][y][x]);
        }
    }
    turnCube(boxIdx,dir);

    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int idx = turnIdx[boxIdx][i];
        int r = turnInfo[boxIdx][i][0];
        int c = turnInfo[boxIdx][i][1];
        for (int j = 0; j < 3; j++) {
            int y = blockIdx[r / 2][c / 2][j][0];
            int x = blockIdx[r / 2][c / 2][j][1];
            myCube[idx][y][x] = myDeq[i*3+j];
        }
    }
    deque <char> empty;
    empty.swap(myDeq);
}

int main() {
    scanf("%d", &T);
    for (int tc = 0; tc < T; tc++) {
        scanf("%d", &N);
        resetCube();
        for (int n = 0; n < N; n++) {
            scanf("%s", howToTurn);
            doNext(howToTurn[0], howToTurn[1]);
        }
        for(int i=0;i<3;i++){
            for (int j = 0; j < 3; j++) {
                printf("%c", myCube[0][i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

실수

모든 경우의 수를 따져서 index를 정교하게 각 배열에 담아야 했는데 경우마다 cube 배열에 접근하는 index가 달라지고 이걸 정하는 데에서 꼬였다. 시간이 매우 오래 소요되었고 틀린 경우가 많아졌다.

'SW > 알고리즘 문제풀이' 카테고리의 다른 글

백준17406 배열돌리기4  (0) 2020.02.16
백준17471 게리맨더링  (0) 2020.02.15
BJ16235 나무재테크  (0) 2020.02.12
BJ12100 2048(Easy)  (0) 2020.02.12
BJ17142 연구소3  (0) 2020.02.11

티스토리툴바