5373번 큐빙
문제
루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다.
큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다.
이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란색, 앞 면은 빨간색, 뒷 면은 오렌지색, 왼쪽 면은 초록색, 오른쪽 면은 파란색이다.
루빅스 큐브를 돌린 방법이 순서대로 주어진다. 이때, 모두 돌린 다음에 가장 윗 면의 색상을 구하는 프로그램을 작성하시오.
위의 그림은 루빅스 큐브를 푼 그림이다. 왼쪽 면은 시계방향으로 조금 돌려져 있는 상태이다.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다. 각 테스트 케이스는 다음과 같이 구성되어져 있다.
- 첫째 줄에 큐브를 돌린 횟수 n이 주어진다. (1 ≤ n ≤ 1000)
- 둘째 줄에는 큐브를 돌린 방법이 주어진다. 각 방법은 공백으로 구분되어져 있으며, 첫 번째 문자는 돌린 면이다. U: 윗 면, D: 아랫 면, F: 앞 면, B: 뒷 면, L: 왼쪽 면, R: 오른쪽 면이다. 두 번째 문자는 돌린 방향이다. +인 경우에는 시계 방향 (그 면을 바라봤을 때가 기준), -인 경우에는 반시계 방향이다.
출력
각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란색은 y, 빨간색은 r, 오렌지색은 o, 초록색은 g, 파란색은 b.
예제 입력
4
1
L-
2
F+ B+
4
U- D- L+ R+
10
L- U- L+ U- L- U- U- L+ U+ U+
예제 출력
rww
rww
rww
bbb
www
ggg
gwg
owr
bwb
gwo
www
rww
해결방법
극악의 시뮬레이션 문제였다... (2시간 반 걸린듯...)
3차원 배열을 통해 루빅스 큐브를 만든 뒤, 총 12가지의 이동을 직접 구현했다
⭐️ 솔루션 ⭐️
이 방법이 맞는지 모르겠지만 Up, Down, Front, Back, Left, Right 각각 시계,반시계 방향으로 움직이는 함수를 총 12개를 구현하였다
음.... 더 간단하게 하는법이 존재하지 않을까 싶지만... 잘모르겠다 흑흑
아래는 루빅스 큐브의 단면도이다 이제 각각 명령에 따라 큐브를 회전시켜야한다
먼저 회전하는 입력받은 면을 시계 또는 반시계 방향으로 회전시켜야한다
void rotateSelf(int ind,char d){
int tmp[3][3];
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
tmp[i][j] = cube[ind][i][j];
}
}
// 시계 방향 회전
if(d == '+'){
int r=0,c=0;
for(int i=2; i>=0; i--){ // 행
for(int j=0; j<3; j++){ // 열
cube[ind][j][i] = tmp[r][c];
c++;
}
r++;
c=0;
}
}
// 반시계 방향 회전
else{
int r=0,c=0;
for(int i=0; i<3; i++){ // 행
for(int j=2; j>=0; j--){ // 열
cube[ind][j][i] = tmp[r][c];
c++;
}
r++;
c=0;
}
}
}
이제 한 면이 회전함에 따라 4면의 하나의 행 또는 열 또한 회전해야한다
Up ⊕ F(1,2,3) → L(1,2,3) → B(9,8,7) → R(1,2,3)
⊖ F(1,2,3) → R(1,2,3) → B(9,8,7) → L(1,2,3)
Down ⊕ F(7,8,9) → R(7,8,9) → B(3,2,1) → L(7,8,9)
⊕ F(7,8,9) → L(7,8,9) → B(3,2,1) → R(7,8,9)
Front ⊕ U(7,8,9) → R(1,4,7) → D(3,2,1) → L(9,6,3)
⊖ U(7,8,9) → L(9,6,3) → D(3,2,1) → R(1,4,7)
Back ⊕ U(1,2,3) → L(7,4,1) → D(9,8,7) → R(3,6,9)
⊖ U(1,2,3) → R(3,6,9) → D(9,8,7) → L(7,4,1)
Left ⊕ U(1,4,7) → F(1,4,7) → D(1,4,7) → B(1,4,7)
⊖ U(1,4,7) → B(1,4,7) → D(1,4,7) → F(1,4,7)
Right ⊕ U(3,6,9) → B(3,6,9) → D(3,6,9) → F(3,6,9)
⊖ U(3,6,9) → F(3,6,9) → D(3,6,9) → B(3,6,9)
이러한 로직으로 이동 메소드를 구현한뒤, 큐브의 Up 단면을 출력해준다
void printCubeTop(){
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
cout << cube[0][i][j];
}
cout << "\n";
}
}
소스코드
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 0
#define INF 987654321
using namespace std;
int testcase,orderCnt;
string s;
char cube[6][3][3];
char tmp[3];
void setCube(){
char color[6] = {'w','y','r','o','g','b'};
for(int c=0; c<6; c++){
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
cube[c][i][j] = color[c];
}
}
}
}
void rotateSelf(int ind,char d){
int tmp[3][3];
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
tmp[i][j] = cube[ind][i][j];
}
}
if(d == '+'){
int r=0,c=0;
for(int i=2; i>=0; i--){ // 행
for(int j=0; j<3; j++){ // 열
cube[ind][j][i] = tmp[r][c];
c++;
}
r++;
c=0;
}
}else{
int r=0,c=0;
for(int i=0; i<3; i++){ // 행
for(int j=2; j>=0; j--){ // 열
cube[ind][j][i] = tmp[r][c];
c++;
}
r++;
c=0;
}
}
}
void URight(){
for(int i=0; i<3; i++) tmp[i] = cube[2][0][i];
for(int i=0; i<3; i++) cube[2][0][i] = cube[5][0][i];
for(int i=0; i<3; i++) cube[5][0][i] = cube[3][2][2-i];
for(int i=0; i<3; i++) cube[3][2][2-i] = cube[4][0][i];
for(int i=0; i<3; i++) cube[4][0][i] = tmp[i];
}
void ULeft(){
for(int i=0; i<3; i++) tmp[i] = cube[2][0][i];
for(int i=0; i<3; i++) cube[2][0][i] = cube[4][0][i];
for(int i=0; i<3; i++) cube[4][0][i] = cube[3][2][2-i];
for(int i=0; i<3; i++) cube[3][2][2-i] = cube[5][0][i];
for(int i=0; i<3; i++) cube[5][0][i] = tmp[i];
}
void DRight(){
for(int i=0; i<3; i++) tmp[i] = cube[2][2][i];
for(int i=0; i<3; i++) cube[2][2][i] = cube[4][2][i];
for(int i=0; i<3; i++) cube[4][2][i] = cube[3][0][2-i];
for(int i=0; i<3; i++) cube[3][0][2-i] = cube[5][2][i];
for(int i=0; i<3; i++) cube[5][2][i] = tmp[i];
}
void DLeft(){
for(int i=0; i<3; i++) tmp[i] = cube[2][2][i];
for(int i=0; i<3; i++) cube[2][2][i] = cube[5][2][i];
for(int i=0; i<3; i++) cube[5][2][i] = cube[3][0][2-i];
for(int i=0; i<3; i++) cube[3][0][2-i] = cube[4][2][i];
for(int i=0; i<3; i++) cube[4][2][i] = tmp[i];
}
void FRight(){
for(int i=0; i<3; i++) tmp[i] = cube[0][2][i];
for(int i=0; i<3; i++) cube[0][2][i] = cube[4][2-i][2];
for(int i=0; i<3; i++) cube[4][2-i][2] = cube[1][0][2-i];
for(int i=0; i<3; i++) cube[1][0][2-i] = cube[5][i][0];
for(int i=0; i<3; i++) cube[5][i][0] = tmp[i];
}
void FLeft(){
for(int i=0; i<3; i++) tmp[i] = cube[0][2][i];
for(int i=0; i<3; i++) cube[0][2][i] = cube[5][i][0];
for(int i=0; i<3; i++) cube[5][i][0] = cube[1][0][2-i];
for(int i=0; i<3; i++) cube[1][0][2-i] = cube[4][2-i][2];
for(int i=0; i<3; i++) cube[4][2-i][2] = tmp[i];
}
void BRight(){
for(int i=0; i<3; i++) tmp[i] = cube[0][0][i];
for(int i=0; i<3; i++) cube[0][0][i] = cube[5][i][2];
for(int i=0; i<3; i++) cube[5][i][2] = cube[1][2][2-i];
for(int i=0; i<3; i++) cube[1][2][2-i] = cube[4][2-i][0];
for(int i=0; i<3; i++) cube[4][2-i][0] = tmp[i];
}
void BLeft(){
for(int i=0; i<3; i++) tmp[i] = cube[0][0][i];
for(int i=0; i<3; i++) cube[0][0][i] = cube[4][2-i][0];
for(int i=0; i<3; i++) cube[4][2-i][0] = cube[1][2][2-i];
for(int i=0; i<3; i++) cube[1][2][2-i] = cube[5][i][2];
for(int i=0; i<3; i++) cube[5][i][2] = tmp[i];
}
void LRight(){
for(int i=0; i<3; i++) tmp[i] = cube[0][i][0];
for(int i=0; i<3; i++) cube[0][i][0] = cube[3][i][0];
for(int i=0; i<3; i++) cube[3][i][0] = cube[1][i][0];
for(int i=0; i<3; i++) cube[1][i][0] = cube[2][i][0];
for(int i=0; i<3; i++) cube[2][i][0] = tmp[i];
}
void LLeft(){
for(int i=0; i<3; i++) tmp[i] = cube[0][i][0];
for(int i=0; i<3; i++) cube[0][i][0] = cube[2][i][0];
for(int i=0; i<3; i++) cube[2][i][0] = cube[1][i][0];
for(int i=0; i<3; i++) cube[1][i][0] = cube[3][i][0];
for(int i=0; i<3; i++) cube[3][i][0] = tmp[i];
}
void RRight(){
for(int i=0; i<3; i++) tmp[i] = cube[0][i][2];
for(int i=0; i<3; i++) cube[0][i][2] = cube[2][i][2];
for(int i=0; i<3; i++) cube[2][i][2] = cube[1][i][2];
for(int i=0; i<3; i++) cube[1][i][2] = cube[3][i][2];
for(int i=0; i<3; i++) cube[3][i][2] = tmp[i];
}
void RLeft(){
for(int i=0; i<3; i++) tmp[i] = cube[0][i][2];
for(int i=0; i<3; i++) cube[0][i][2] = cube[3][i][2];
for(int i=0; i<3; i++) cube[3][i][2] = cube[1][i][2];
for(int i=0; i<3; i++) cube[1][i][2] = cube[2][i][2];
for(int i=0; i<3; i++) cube[2][i][2] = tmp[i];
}
void rotateCube(char side,char dir){
if(side == 'U'){
rotateSelf(0, dir);
if(dir == '+') URight();
else ULeft();
}
else if(side == 'D'){
rotateSelf(1, dir);
if(dir == '+') DRight();
else DLeft();
}
else if(side == 'F'){
rotateSelf(2, dir);
if(dir == '+') FRight();
else FLeft();
}
else if(side == 'B'){
rotateSelf(3, dir);
if(dir == '+') BRight();
else BLeft();
}
else if(side == 'L'){
rotateSelf(4, dir);
if(dir == '+') LRight();
else LLeft();
}
else if(side == 'R'){
rotateSelf(5, dir);
if(dir == '+') RRight();
else RLeft();
}
}
void printCubeTop(){
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
cout << cube[0][i][j];
}
cout << "\n";
}
}
int main(int argc, const char * argv[]) {
// cin,cout 속도향상
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> testcase;
for(int t=0; t<testcase; t++){
// 초기 큐브 상태 저장
setCube();
// 회전 명령 입력
cin >> orderCnt;
for(int i=0; i<orderCnt; i++){
cin >> s;
rotateCube(s[0],s[1]);
}
printCubeTop();
}
return 0;
}
'Algorithm > BOJ 문제풀이' 카테고리의 다른 글
| [BFS] 5214번 환승 (0) | 2019.01.11 |
|---|---|
| [BFS] 12761번 돌다리 (0) | 2019.01.10 |
| [SIM] 15662번 톱니바퀴 (2) (0) | 2019.01.09 |
| [SIM] 14891번 톱니바퀴 (0) | 2019.01.09 |
| [SIM] 14999번 주사위 굴리기 (0) | 2019.01.09 |
