문제 링크
https://www.acmicpc.net/problem/5373
5373번: 큐빙
문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면
www.acmicpc.net
문제 접근
모든 면에 대한 색상을 큐브를 돌릴 때 마다 일일히 바꿔주는 것은 고려해야할 것이 너무 많다고 생각했습니다. 제가 접근한 방법은 3x3x3의 큐브의 각 단위에 해당하는 '작은 큐브'를 정의하는 것이었습니다. '작은 큐브'는 쉽게 말해서 정육면체이며, 6가지 면에 대한 색상 정보를 담습니다.
typedef struct cuve {
char top, front, bot, back, left, right;
};위의 작은 큐브를 통해서 3x3x3의 큐브를 만들어 줍니다.
cuve cuv[3][3][3];그리고 모든 작은 큐브에 대하여 동일하게 초기화 해줍니다.
void init_cuve() {
for (int h = 0; h < 3; ++h) {
for (int y = 0; y < 3; ++y) {
for (int x = 0; x < 3; ++x) {
cuv[h][y][x].top = 'w';
cuv[h][y][x].bot = 'y';
cuv[h][y][x].front = 'r';
cuv[h][y][x].back = 'o';
cuv[h][y][x].left = 'g';
cuv[h][y][x].right = 'b';
}
}
}
}각 작은 큐브는 표면에 노출된 면만 고정적으로 노출되므로 보이지 않는 면을 초기화 한다해도 문제 없습니다.
이제 큐브 정의가 끝났습니다. 이제 면(side)과 방향(direction)을 입력받아서 큐브를 회전하는 함수를 짜봅시다.
회전의 정의는 큐브의 회전은 '각 면을 정면에서 바라보았을 때의 시계/반시계 방향'으로 이루어진다고 나와있습니다.
그 말을 각 면에 대해서 그림을 그려본다면, 앞(F)면을 시계방향으로 회전하는 것과, 뒷(B)면을 반시계방향으로 회전하는 것의 방향이 같음을 알 수 있습니다. 또한 (h, y, x)의 좌표계에서 바라보면 앞면과 뒷면은 h좌표가 고정이고, (x, y)좌표만 움직임을 알 수 있습니다. 이를 정리하면 아래와 같습니다.
- 윗면(U)/아랫면(D) : h고정(0 또는 2) xy가변, (방향관점) 윗면 시계방향 = 아랫면 반시계방향
- 앞면(F)/뒷면(B) : y고정(0 또는 2), hx가변, (방향관점) 앞면 시계방향 = 뒷면 반시계방향
- 왼쪽(L)/오른쪽(R) : x고정(0 또는 2), hy가변, (방향관점) 왼쪽 시계방향 = 오른쪽 반시계방향
이제 어떤 면을 선택하였을때 어떻게 좌표 접근을 해야할지 해결하였습니다.
이제 시계/반시계 방향으로 회전하는 것을 알아봅시다.
(h, y, x)로 좌표를 표현하면 위 사진과 같습니다. 윗면을 시계방향(h고정, xy가변)으로 회전하면
- (0, 0, 0) -> (0, 0, 2)로 이동합니다.
- (0, 1, 0) -> (0, 0, 1)로 이동합니다. y가 1증가 -> x가 1감소
- (0, 1, 1) -> (0, 1, 1)로 이동합니다. x가 1증가 -> y가 1증가
규칙이 보이시나요? 코드로 표현하면 아래와 같습니다. (색상은 밑에서 회전하겠습니다)
new_cuve[h][x][2 - y] = cuv[h][y][x];위의 방법으로 다른 모든 면과 방향에 대해서 정의해줍니다.
윗면 시계 || 아랫면 반시계 = new_cuve[h][x][2 - y] = cuv[h][y][x];
윗면 반시계 || 아랫면 시계 = new_cuve[h][2 - x][y] = cuv[h][y][x];
앞면 시계 || 뒷면 반시계 = new_cuve[x][y][2 - h] = cuv[h][y][x];
앞면 반시계 || 뒷면 시계 = new_cuve[2 - x][y][h] = cuv[h][y][x];
오른쪽 시계 || 왼쪽 반시계 = new_cuve[2 - y][h][x] = cuv[h][y][x];
오른쪽 반시계 || 왼쪽 시계 = new_cuve[y][2 - h][x] = cuv[h][y][x];
자 이제 방향과 좌표 정리가 끝났습니다. 이제 남은건 회전하면서 작은 큐브의 색상도 회전해주는 일입니다.
이 부분은 각 면마다 작은 큐브가 회전하는 방향이 달라서 규칙을 찾는데 실패했습니다. 하지만 매우 간단한 코드이기 때문에 괜찮습니다..
윗면 시계 || 아랫면 반시계 = back -> right -> front -> left -> back같은 순으로 4가지 색상을 옮겨주기만 하면 됩니다!
이 부분에 더 좋은 접근 방법이 있다면 다른 글을 참고해주세요. 저는 생각이 나지 않았습니다..
윗면 반시계 || 아랫면 시계 = back -> left -> front -> right -> back
앞면 시계 || 뒷면 반시계 = top -> right -> bot -> left -> top
앞면 반시계 || 뒷면 시계 = top -> left -> bot -> right -> top
오른쪽 시계 || 왼쪽 반시계 = top -> back -> bot -> front -> top
오른쪽 반시계 || 왼쪽 시계 = top -> front -> bot -> back -> top
회전 소스 코드는 아래와 같습니다.
// 큐브 from에서 큐브 to로 값을 복사
void copy_cuve(cuve from[][3][3], cuve to[][3][3]) {
int h, y, x;
for (h = 0; h < 3; ++h)
for (y = 0; y < 3; ++y)
for (x = 0; x < 3; ++x)
to[h][y][x] = from[h][y][x];
}
// 명령어를 입력받고 면을 회전하는 코드 (side: 면, direction: 시계/반시계)
void rotate(char side, char direction) {
char temp;
int h, y, x;
cuve new_cuve[3][3][3];
copy_cuve(cuv, new_cuve);
if (side == 'U' || side == 'D') { // 윗면 또는 아랫면인 경우 (h고정, yx가변)
h = (side == 'U' ? 0 : 2); // 높이 고정
if ((direction == '+' && side == 'U') ||
(direction == '-' && side == 'D')) {
// 윗면 시계, 바닥면 반시계
for (y = 0; y < 3; ++y) {
for (x = 0; x < 3; ++x) {
// back -> right -> front -> left -> back
temp = cuv[h][y][x].left;
cuv[h][y][x].left = cuv[h][y][x].front;
cuv[h][y][x].front = cuv[h][y][x].right;
cuv[h][y][x].right = cuv[h][y][x].back;
cuv[h][y][x].back = temp;
new_cuve[h][x][2 - y] = cuv[h][y][x];
}
}
}
else { // 윗면 반시계, 바닥면 시계
for (y = 0; y < 3; ++y) {
for (x = 0; x < 3; ++x) {
// back -> left -> front -> right -> back
temp = cuv[h][y][x].right;
cuv[h][y][x].right = cuv[h][y][x].front;
cuv[h][y][x].front = cuv[h][y][x].left;
cuv[h][y][x].left = cuv[h][y][x].back;
cuv[h][y][x].back = temp;
new_cuve[h][2 - x][y] = cuv[h][y][x];
}
}
}
}
else if (side == 'F' || side == 'B') { // 앞면 또는 뒷면인 경우 (y고정, hx가변)
y = (side == 'F' ? 2 : 0); // y 고정 (앞면: 2, 뒷면: 0)
if ((direction == '+' && side == 'F') ||
(direction == '-' && side == 'B')) { // 앞면 시계, 뒷면 반시계
for (h = 0; h < 3; ++h) {
for (x = 0; x < 3; ++x) {
// top -> right -> bot -> left -> top
temp = cuv[h][y][x].left;
cuv[h][y][x].left = cuv[h][y][x].bot;
cuv[h][y][x].bot = cuv[h][y][x].right;
cuv[h][y][x].right = cuv[h][y][x].top;
cuv[h][y][x].top = temp;
new_cuve[x][y][2 - h] = cuv[h][y][x];
}
}
}
else { // 앞면 반시계, 뒷면 시계
for (h = 0; h < 3; ++h) {
for (x = 0; x < 3; ++x) {
// top -> left -> bot -> right -> top
temp = cuv[h][y][x].right;
cuv[h][y][x].right = cuv[h][y][x].bot;
cuv[h][y][x].bot = cuv[h][y][x].left;
cuv[h][y][x].left = cuv[h][y][x].top;
cuv[h][y][x].top = temp;
new_cuve[2 - x][y][h] = cuv[h][y][x];
}
}
}
}
else if (side == 'L' || side == 'R') { // 왼쪽 또는 오른쪽 (x고정, hy가변)
x = (side == 'L' ? 0 : 2); // x 고정 (왼쪽: 0, 오른쪽: 2)
if ((direction == '+' && side == 'R') ||
(direction == '-' && side == 'L')) {
// 오른쪽 시계, 왼쪽 반시계
for (h = 0; h < 3; ++h) {
for (y = 0; y < 3; ++y) {
// top -> back -> bot -> front -> top
temp = cuv[h][y][x].front;
cuv[h][y][x].front = cuv[h][y][x].bot;
cuv[h][y][x].bot = cuv[h][y][x].back;
cuv[h][y][x].back = cuv[h][y][x].top;
cuv[h][y][x].top = temp;
new_cuve[2 - y][h][x] = cuv[h][y][x];
}
}
}
else { // 오른쪽 반시계, 왼쪽 시계
for (h = 0; h < 3; ++h) {
for (y = 0; y < 3; ++y) {
// top -> front -> bot -> back -> top
temp = cuv[h][y][x].back;
cuv[h][y][x].back = cuv[h][y][x].bot;
cuv[h][y][x].bot = cuv[h][y][x].front;
cuv[h][y][x].front = cuv[h][y][x].top;
cuv[h][y][x].top = temp;
new_cuve[y][2 - h][x] = cuv[h][y][x];
}
}
}
}
copy_cuve(new_cuve, cuv); // new -> cuv로 copy
}
소스 코드
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct cuve {
char top, front, bot, back, left, right;
};
cuve cuv[3][3][3];
void init_cuve() {
for (int h = 0; h < 3; ++h) {
for (int y = 0; y < 3; ++y) {
for (int x = 0; x < 3; ++x) {
cuv[h][y][x].top = 'w';
cuv[h][y][x].bot = 'y';
cuv[h][y][x].front = 'r';
cuv[h][y][x].back = 'o';
cuv[h][y][x].left = 'g';
cuv[h][y][x].right = 'b';
}
}
}
}
// 큐브 from에서 큐브 to로 값을 복사
void copy_cuve(cuve from[][3][3], cuve to[][3][3]) {
int h, y, x;
for (h = 0; h < 3; ++h)
for (y = 0; y < 3; ++y)
for (x = 0; x < 3; ++x)
to[h][y][x] = from[h][y][x];
}
// 명령어를 입력받고 면을 회전하는 코드 (side: 면, direction: 시계/반시계)
void rotate(char side, char direction) {
char temp;
int h, y, x;
cuve new_cuve[3][3][3];
copy_cuve(cuv, new_cuve);
if (side == 'U' || side == 'D') { // 윗면 또는 아랫면인 경우 (h고정, yx가변)
h = (side == 'U' ? 0 : 2); // 높이 고정
if ((direction == '+' && side == 'U') ||
(direction == '-' && side == 'D')) {
// 윗면 시계, 바닥면 반시계
for (y = 0; y < 3; ++y) {
for (x = 0; x < 3; ++x) {
// back -> right -> front -> left -> back
temp = cuv[h][y][x].left;
cuv[h][y][x].left = cuv[h][y][x].front;
cuv[h][y][x].front = cuv[h][y][x].right;
cuv[h][y][x].right = cuv[h][y][x].back;
cuv[h][y][x].back = temp;
new_cuve[h][x][2 - y] = cuv[h][y][x];
}
}
}
else { // 윗면 반시계, 바닥면 시계
for (y = 0; y < 3; ++y) {
for (x = 0; x < 3; ++x) {
// back -> left -> front -> right -> back
temp = cuv[h][y][x].right;
cuv[h][y][x].right = cuv[h][y][x].front;
cuv[h][y][x].front = cuv[h][y][x].left;
cuv[h][y][x].left = cuv[h][y][x].back;
cuv[h][y][x].back = temp;
new_cuve[h][2 - x][y] = cuv[h][y][x];
}
}
}
}
else if (side == 'F' || side == 'B') { // 앞면 또는 뒷면인 경우 (y고정, hx가변)
y = (side == 'F' ? 2 : 0); // y 고정 (앞면: 2, 뒷면: 0)
if ((direction == '+' && side == 'F') ||
(direction == '-' && side == 'B')) { // 앞면 시계, 뒷면 반시계
for (h = 0; h < 3; ++h) {
for (x = 0; x < 3; ++x) {
// top -> right -> bot -> left -> top
temp = cuv[h][y][x].left;
cuv[h][y][x].left = cuv[h][y][x].bot;
cuv[h][y][x].bot = cuv[h][y][x].right;
cuv[h][y][x].right = cuv[h][y][x].top;
cuv[h][y][x].top = temp;
new_cuve[x][y][2 - h] = cuv[h][y][x];
}
}
}
else { // 앞면 반시계, 뒷면 시계
for (h = 0; h < 3; ++h) {
for (x = 0; x < 3; ++x) {
// top -> left -> bot -> right -> top
temp = cuv[h][y][x].right;
cuv[h][y][x].right = cuv[h][y][x].bot;
cuv[h][y][x].bot = cuv[h][y][x].left;
cuv[h][y][x].left = cuv[h][y][x].top;
cuv[h][y][x].top = temp;
new_cuve[2 - x][y][h] = cuv[h][y][x];
}
}
}
}
else if (side == 'L' || side == 'R') { // 왼쪽 또는 오른쪽 (x고정, hy가변)
x = (side == 'L' ? 0 : 2); // x 고정 (왼쪽: 0, 오른쪽: 2)
if ((direction == '+' && side == 'R') ||
(direction == '-' && side == 'L')) {
// 오른쪽 시계, 왼쪽 반시계
for (h = 0; h < 3; ++h) {
for (y = 0; y < 3; ++y) {
// top -> back -> bot -> front -> top
temp = cuv[h][y][x].front;
cuv[h][y][x].front = cuv[h][y][x].bot;
cuv[h][y][x].bot = cuv[h][y][x].back;
cuv[h][y][x].back = cuv[h][y][x].top;
cuv[h][y][x].top = temp;
new_cuve[2 - y][h][x] = cuv[h][y][x];
}
}
}
else { // 오른쪽 반시계, 왼쪽 시계
for (h = 0; h < 3; ++h) {
for (y = 0; y < 3; ++y) {
// top -> front -> bot -> back -> top
temp = cuv[h][y][x].back;
cuv[h][y][x].back = cuv[h][y][x].bot;
cuv[h][y][x].bot = cuv[h][y][x].front;
cuv[h][y][x].front = cuv[h][y][x].top;
cuv[h][y][x].top = temp;
new_cuve[y][2 - h][x] = cuv[h][y][x];
}
}
}
}
copy_cuve(new_cuve, cuv); // new -> cuv로 copy
}
void print_cuve() {
for (int y = 0; y < 3; ++y) {
for (int x = 0; x < 3; ++x) {
cout << cuv[0][y][x].top;
}
cout << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T, N;
char side, direction;
cin >> T;
for (int t = 0; t < T; ++t) {
init_cuve();
cin >> N;
for (int i = 0; i < N; ++i) {
cin >> side >> direction;
rotate(side, direction);
}
print_cuve();
}
return 0;
}
개발 환경 : VS2019
질문, 지적 환영합니다!
'알고리즘 > 백준' 카테고리의 다른 글
| [C++] 백준 17837 새로운 게임 2 (0) | 2020.05.29 |
|---|---|
| [C++] 백준 1520 내리막길 (0) | 2020.05.26 |
| [C++] 백준 13460 구슬 탈출 2 (0) | 2020.05.26 |
| [C++] 백준 15684 사다리 조작 (0) | 2020.05.25 |
| [C++] 백준 14891 톱니바퀴 (0) | 2020.05.25 |
