[BOJ 5373] 큐빙

https://www.acmicpc.net/problem/5373

5373번: 큐빙

 

- 문제 요약

 

문제에서는 3x3 사이즈의 큐브가 주어진다.

윗 면은 흰색, 아랫면은 노란색, 앞 면은 빨간색, 뒷 면은 오렌지색, 왼쪽 면은 초록색, 오른쪽 면은 파란색이다.

n이 주어지고(1<=n<=1000) 다음 n개의 줄에 큐브를 돌린 방법이 순서대로 주어진다.

모두 돌린 후 가장 윗면의 색상을 구하시오.

 

<입력>

각 방법은 공백으로 구분되어져 있으며, 첫 번째 문자는 돌린 면이다.

U: 윗 면, D: 아랫 면, F: 앞 면, B: 뒷 면, L: 왼쪽 면, R: 오른쪽 면이다.

두 번째 문자는 돌린 방향이다. +인 경우에는 시계 방향 (그 면을 바라봤을 때가 기준), -인 경우에는 반시계 방향이다.

 

<출력>

첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다.

흰색은 w, 노란색은 y, 빨간색은 r, 오렌지색은 o, 초록색은 g, 파란색은 b로 표현한다.

 

 

- 알고리즘 정리

 

우선 딱 보기에는 그냥 노가다 문제 그 자체인 것 같습니다.

알고리즘보단 어떻게 큐브의 인덱스를 잡을 것인가... 가 문제가 될 것 같습니다.

 

실제 큐브를 돌려가면서 코드를 짜는게 가장 좋을 것 같지만, 저는 집에 큐브가 없기에 온라인 사이트를 이용했습니다.

https://rubiks-cube-solver.com/ko/#

루빅 큐브 맞추기

 

조금이라도 코드를 줄이기 위해, 큐브를 돌려가며 생각을 해봤습니다.

알파벳 뒤에 주어지는 +와 -는 돌린 방향을 뜻한다고 문제에 나와있습니다.

여기서 반시계 방향인 -를 구현 할 때는 시계 방향으로 세 번 돌리면 반시계 방향으로 구현한 결과와 같게 나옵니다.

 

큐브의 면은 여러가지 방법으로 구현할 수 있겠지만, 저는 그냥 2차원 배열을 6개 만들겠습니다.

 

 

- 코드 작성

 

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int n,t,ssss=3;
string a;
char up[3][3]={{'w','w','w'},{'w','w','w'},{'w','w','w'}};
char down[3][3]={{'y','y','y'},{'y','y','y'},{'y','y','y'}};
char ff[3][3]={{'r','r','r'},{'r','r','r'},{'r','r','r'}};
char backward[3][3]={{'o','o','o'},{'o','o','o'},{'o','o','o'}};
char ll[3][3]={{'g','g','g'},{'g','g','g'},{'g','g','g'}};
char rr[3][3]={{'b','b','b'},{'b','b','b'},{'b','b','b'}};
char tmp;

void cube(){
   for(int i=0;i<3;i++){
      for(int j=0;j<3;j++){
         cout<<up[i][j];
      }
      cout<<endl;
   }
}

void set(){
	fill(up[0],up[3],'w');
	fill(down[0],down[3],'y');
	fill(ff[0],ff[3],'r');
	fill(backward[0],backward[3],'o');
	fill(ll[0],ll[3],'g');
	fill(rr[0],rr[3],'b');
}

void fup(){
	char w[3],u[3];
	w[0]=rr[0][0];
	w[1]=rr[0][1];
	w[2]=rr[0][2];//파 
	u[0]=ff[0][0];
	u[1]=ff[0][1];
	u[2]=ff[0][2];//빨 
	ff[0][0]=w[0];
	ff[0][1]=w[1];
	ff[0][2]=w[2];
	w[0]=ll[0][0];
	w[1]=ll[0][1];
	w[2]=ll[0][2];//초
	ll[0][0]=u[0]; 
	ll[0][1]=u[1];
	ll[0][2]=u[2];
	u[0]=backward[0][0];
	u[1]=backward[0][1];
	u[2]=backward[0][2];//주 
	backward[0][0]=w[0]; 
	backward[0][1]=w[1];
	backward[0][2]=w[2];
	rr[0][0]=u[0];
	rr[0][1]=u[1];
	rr[0][2]=u[2];
	for(int i=0;i<ssss/2;i++){
		for(int j=i;j<ssss-i-1;j++){
			tmp=up[ssss-j-1][i];
			up[ssss-j-1][i]=up[ssss-i-1][ssss-j-1];
			up[ssss-i-1][ssss-j-1]=up[j][ssss-i-1];
			up[j][ssss-i-1]=up[i][j];
			up[i][j]=tmp;
		}
	}
}

void fum(){ 
   fup();
   fup();
   fup();
}

void fdp(){
    char w[3],u[3];
	w[0]=ff[2][0];
	w[1]=ff[2][1];
	w[2]=ff[2][2];//빨 
	u[0]=rr[2][0];
	u[1]=rr[2][1];
	u[2]=rr[2][2];//파 
	rr[2][0]=w[0];
	rr[2][1]=w[1];
	rr[2][2]=w[2];
	w[0]=backward[2][0]; 
	w[1]=backward[2][1]; 
	w[2]=backward[2][2];//주
	backward[2][0]=u[0];
	backward[2][1]=u[1];
	backward[2][2]=u[2];
	u[0]=ll[2][0];
	u[1]=ll[2][1];
	u[2]=ll[2][2];//초 
	ll[2][0]=w[0];
	ll[2][1]=w[1];
	ll[2][2]=w[2];
	ff[2][0]=u[0];
	ff[2][1]=u[1];
	ff[2][2]=u[2];
	for(int i=0;i<ssss/2;i++){
		for(int j=i;j<ssss-i-1;j++){
			tmp=down[ssss-j-1][i];
			down[ssss-j-1][i]=down[ssss-i-1][ssss-j-1];
			down[ssss-i-1][ssss-j-1]=down[j][ssss-i-1];
			down[j][ssss-i-1]=down[i][j];
			down[i][j]=tmp;
		}
	}
}

void fdm(){
   fdp();
   fdp();
   fdp();
}

void ffp(){
   char w[3],u[3];
   w[0]=up[2][0];
   w[1]=up[2][1];
   w[2]=up[2][2];//흰 
   u[0]=rr[0][0];
   u[1]=rr[1][0];
   u[2]=rr[2][0];//파 
   rr[0][0]=w[0]; 
   rr[1][0]=w[1];
   rr[2][0]=w[2];
   w[0]=down[2][0];
   w[1]=down[2][1];
   w[2]=down[2][2];//노
   down[2][0]=u[0];
   down[2][1]=u[1];
   down[2][2]=u[2];
   u[0]=ll[2][2];
   u[1]=ll[1][2];
   u[2]=ll[0][2];//초 
   ll[2][2]=w[0];
   ll[1][2]=w[1];
   ll[0][2]=w[2];
   up[2][0]=u[0]; 
   up[2][1]=u[1]; 
   up[2][2]=u[2]; 
   for(int i=0;i<ssss/2;i++){
		for(int j=i;j<ssss-i-1;j++){
			tmp=ff[ssss-j-1][i];
			ff[ssss-j-1][i]=ff[ssss-i-1][ssss-j-1];
			ff[ssss-i-1][ssss-j-1]=ff[j][ssss-i-1];
			ff[j][ssss-i-1]=ff[i][j];
			ff[i][j]=tmp;
		}
	}
}

void ffm(){
   ffp();
   ffp();
   ffp();
}

void fbp(){
   char w[3],u[3];
   w[0]=up[0][0];
   w[1]=up[0][1];
   w[2]=up[0][2];//흰 
   u[0]=ll[2][0];
   u[1]=ll[1][0];
   u[2]=ll[0][0];//초
   ll[2][0]=w[0]; 
   ll[1][0]=w[1];
   ll[0][0]=w[2];
   w[0]=down[0][0];
   w[1]=down[0][1];
   w[2]=down[0][2];//노
   down[0][0]=u[0];
   down[0][1]=u[1];
   down[0][2]=u[2];
   u[0]=rr[0][2];
   u[1]=rr[1][2];
   u[2]=rr[2][2];//파 
   rr[0][2]=w[0];
   rr[1][2]=w[1];
   rr[2][2]=w[2];
   up[0][0]=u[0];
   up[0][1]=u[1];
   up[0][2]=u[2];
   for(int i=0;i<ssss/2;i++){
		for(int j=i;j<ssss-i-1;j++){
			tmp=backward[ssss-j-1][i];
			backward[ssss-j-1][i]=backward[ssss-i-1][ssss-j-1];
			backward[ssss-i-1][ssss-j-1]=backward[j][ssss-i-1];
			backward[j][ssss-i-1]=backward[i][j];
			backward[i][j]=tmp;
		}
	}
}

void fbm(){
   fbp();
   fbp();
   fbp();
}

void flp(){
   char w[3],u[3];
   w[0]=up[0][0];
   w[1]=up[1][0];
   w[2]=up[2][0];//흰 
   u[0]=ff[0][0];
   u[1]=ff[1][0];
   u[2]=ff[2][0];//빨 
   ff[0][0]=w[0]; 
   ff[1][0]=w[1];
   ff[2][0]=w[2];
   w[0]=down[2][2];
   w[1]=down[1][2];
   w[2]=down[0][2];//노
   down[2][2]=u[0]; 
   down[1][2]=u[1];
   down[0][2]=u[2];
   u[0]=backward[2][2];
   u[1]=backward[1][2];
   u[2]=backward[0][2];//주
   backward[2][2]=w[0]; 
   backward[1][2]=w[1];
   backward[0][2]=w[2];
   up[0][0]=u[0];
   up[1][0]=u[1];
   up[2][0]=u[2];
   for(int i=0;i<ssss/2;i++){
		for(int j=i;j<ssss-i-1;j++){
			tmp=ll[ssss-j-1][i];
			ll[ssss-j-1][i]=ll[ssss-i-1][ssss-j-1];
			ll[ssss-i-1][ssss-j-1]=ll[j][ssss-i-1];
			ll[j][ssss-i-1]=ll[i][j];
			ll[i][j]=tmp;
		}
	}
}

void flm(){
   flp();
   flp();
   flp();
}

void frp(){
	char w[3],u[3];
	w[0]=ff[2][2];
	w[1]=ff[1][2];
	w[2]=ff[0][2];//빨 
	u[0]=up[2][2];
	u[1]=up[1][2];
	u[2]=up[0][2];//흰 
	up[2][2]=w[0];
	up[1][2]=w[1];
	up[0][2]=w[2];
	w[0]=backward[0][0];
	w[1]=backward[1][0];
	w[2]=backward[2][0];//주
	backward[0][0]=u[0];
	backward[1][0]=u[1];
	backward[2][0]=u[2];
	u[0]=down[0][0];
	u[1]=down[1][0];
	u[2]=down[2][0];//노 
	down[0][0]=w[0];
	down[1][0]=w[1];
	down[2][0]=w[2];
	ff[2][2]=u[0];
	ff[1][2]=u[1];
	ff[0][2]=u[2];
	for(int i=0;i<ssss/2;i++){
		for(int j=i;j<ssss-i-1;j++){
			tmp=rr[ssss-j-1][i];
			rr[ssss-j-1][i]=rr[ssss-i-1][ssss-j-1];
			rr[ssss-i-1][ssss-j-1]=rr[j][ssss-i-1];
			rr[j][ssss-i-1]=rr[i][j];
			rr[i][j]=tmp;
		}
	}
}

void frm(){
   frp();
   frp();
   frp();
}

int main(){
   cin>>n;
   for(int i=0;i<n;i++){
      cin>>t;
      for(int j=0;j<t;j++){
         cin>>a;
         if(a=="U+"){
            fup();
         }
         else if(a=="U-"){
            fum();
         }
         else if(a=="D+"){
            fdp();
         }
         else if(a=="D-"){
            fdm();
         }
         else if(a=="F+"){
            ffp();
         }
         else if(a=="F-"){
            ffm();
         }
         else if(a=="B+"){
            fbp();
         }
         else if(a=="B-"){
            fbm();
         }
         else if(a=="L+"){
            flp();
         }
         else if(a=="L-"){
            flm();
         }
         else if(a=="R+"){
            frp();
         }
         else if(a=="R-"){
            frm();
         }
      }
      cube();
      set();
   }
}

 

함수 중간중간 들어있는 for문은 큐브 면을 90도 회전시키는 코드입니다.

저거 안넣어서 1시간 날렸습니다.....

 

코드 제출 결과

이 문제 푸는데 5~6시간 걸린 것 같습니다.....

코드 짜는데 2시간, 멘탈 나가서 실수한 거 고치는 거에 1~2시간, 1차 디버깅에 1시간, 2차 디버깅에 1시간....

 

시뮬레이션 카테고리에 있는 문제들이 재밌어보여서 풀어봤는데.... 당분간 거들떠도 보지 않으려고요.

그냥 DP나 풀겠습니다......