[5373번]
https://www.acmicpc.net/problem/5373
머리 속으로만 풀려고 머리 속에서 큐브를 이리저리 돌려보다 실패하여 전개도를 그려서 풀어보았다. 전개도를 이용하여 L/R, U/D, F/B 방향으로 회전할 때 어느 흐름으로 숫자가 회전해야 하는지 알아내면 생각보다 금방 풀렸다. 특별한 알고리즘 사용없이 구현으로만 승부하는 쉽지 않은 구현 문제였다.
풀이 방법
1.
전개도를 십자가 모양으로 그리고(굳이 십자가 모양 전개도는 아니어도 된다) 전개도 위에 1~12까지 숫자를 써놓는다. 여기서 큐브 위의 모습과 전개도 상의 모습을 헷갈리면 안 된다. 큐브에서는 자연스럽게 1~12로 이어지는 숫자가 전개도 상에서는 띄엄띄엄 써있을 수 있다.
전개도 상에서 빨간색 숫자와 화살표가 L+ 방향으로 회전하기 전에 써있는 숫자 순서이다(같은 방식으로 파란색은 U+, 초록색은 F+).
L+ 방향의 경우 큐브와 전개도가 이질감이 없지만 U+와 F+의 경우 띄엄띄엄 써있는 것을 확인할 수 있다.
2.
전개도 상의 1~12 순서에 맞게 주어진 큐브의 숫자를 배열 var에 담고, rotate(var+1,var+10,var+13)을 이용하여 열 번째 숫자가 가장 첫 번째로 오도록 배열을 회전시킨다.
그 이후 회전된 배열 var을 숫자를 담았던 순서와 같은 순서로 큐브에 대입한다. 이로써 회전 한 번이 구현되었다.
3.
+방향 회전 3번이면 -방향과 같아진다는 점을 이용하여 -방향 회전은 +방향 회전 메서드를 3번 호출하여 구현한다.
4.
큐브가 돌면 돌아가는 중심축이 되는 큐브 면도 그에 맞게 회전해야 한다. 이건 마치 3*3 행렬을 시계(혹은 반시계) 방향으로 회전시키는 것과 같다. 이 부분은 matRotation(int face, int d) 메서드로 구현하였다.
5.
move(char f, int d) 메서드 안에 +/- 방향에 유의하며 알맞게 if/else if문으로 경우를 모두 나눠주고 위에서 만들어 놓은 회전 메서드를 알맞게 배치하면 구현이 완료된다.
6.
마지막으로 맨 윗면을 출력하는 메서드를 호출해준다.
C++ 코드
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility> // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;
int T;
int n;
char r[3];
char cube[7][4][4];
void showFace(int i) {
for(int j=1;j<=3;++j) {
for(int k=1;k<=3;++k) {
printf("%c", cube[i][j][k]);
}
printf("\n");
}
return;
}
void matRotation(int face, int d) {
char phase[4][4];
memset(phase, 0, sizeof(phase));
for(int j=1;j<=3;++j) {
for(int k=1;k<=3;++k) {
phase[j][k] = cube[face][j][k];
}
}
if(d > 0) { // clockwise
for(int i=0;i<4;++i) {
if(i == 0) {
for(int j=1;j<=3;++j) {
cube[face][j][3] = phase[1][j];
}
} else if(i==1) {
for(int j=1;j<=3;++j) {
cube[face][3][4-j] = phase[j][3];
}
} else if(i==2) {
for(int j=1;j<=3;++j) {
cube[face][4-j][1] = phase[3][4-j];
}
} else {
for(int j=1;j<=3;++j) {
cube[face][1][j] = phase[4-j][1];
}
}
}
} else if(d == 0) { // counter-clockwise
for(int i=0;i<4;++i) {
if(i==0) {
for(int j=1;j<=3;++j) {
cube[face][j][1] = phase[1][4-j];
}
} else if(i==1) {
for(int j=1;j<=3;++j) {
cube[face][3][j] = phase[j][1];
}
} else if(i==2) {
for(int j=1;j<=3;++j) {
cube[face][4-j][3] = phase[3][j];
}
} else {
for(int j=1;j<=3;++j) {
cube[face][1][4-j] = phase[4-j][3];
}
}
}
}
return;
}
void color(int i, char c) {
for(int j=1;j<=3;++j) {
for(int k=1;k<=3;++k) {
cube[i][j][k] = c;
}
}
return;
}
void initCube() {
memset(cube, 0, sizeof(cube));
for(int i=1;i<=6;++i) {
switch(i) {
case 1:
color(1,'w');
break;
case 2:
color(2,'r');
break;
case 3:
color(3,'y');
break;
case 4:
color(4,'o');
break;
case 5:
color(5,'g');
break;
case 6:
color(6,'b');
break;
}
}
return;
}
void moveL() { // L+
char var[13];
memset(var, 0, sizeof(var));
int idx = 1;
int faces[] = {1,2,3,4};
for(int i=0;i<4;++i) {
int face = faces[i];
for(int j=1;j<=3;++j) {
var[idx++] = cube[face][j][1];
}
}
rotate(var+1,var+10,var+13);
idx = 1;
for(int i=0;i<4;++i) {
int face = faces[i];
for(int j=1;j<=3;++j) {
cube[face][j][1] = var[idx++];
}
}
return;
}
void moveR() { // R-
char var[13];
memset(var, 0, sizeof(var));
int idx = 1;
int faces[] = {1,2,3,4};
for(int i=0;i<4;++i) {
int face = faces[i];
for(int j=1;j<=3;++j) {
var[idx++] = cube[face][j][3];
}
}
rotate(var+1,var+10,var+13);
idx = 1;
for(int i=0;i<4;++i) {
int face = faces[i];
for(int j=1;j<=3;++j) {
cube[face][j][3] = var[idx++];
}
}
return;
}
void moveU() { // U+
int var[13];
memset(var,0,sizeof(var));
int idx = 1;
int faces[] = {4,6,2,5};
for(int i=0;i<4;++i) {
int face = faces[i];
for(int j=1;j<=3;++j) {
if(face == 4) {
var[idx++] = cube[face][3][j];
} else {
var[idx++] = cube[face][1][4-j];
}
}
}
rotate(var+1,var+10,var+13);
idx = 1;
for(int i=0;i<4;++i) {
int face = faces[i];
for(int j=1;j<=3;++j) {
if(face == 4) {
cube[face][3][j] = var[idx++];
} else {
cube[face][1][4-j] = var[idx++];
}
}
}
return;
}
void moveD() { // D-
int var[13];
memset(var,0,sizeof(var));
int idx = 1;
int faces[] = {4,6,2,5};
for(int i=0;i<4;++i) {
int face = faces[i];
for(int j=1;j<=3;++j) {
if(face == 4) {
var[idx++] = cube[face][1][j];
} else {
var[idx++] = cube[face][3][4-j];
}
}
}
rotate(var+1,var+10,var+13);
idx = 1;
for(int i=0;i<4;++i) {
int face = faces[i];
for(int j=1;j<=3;++j) {
if(face == 4) {
cube[face][1][j] = var[idx++];
} else {
cube[face][3][4-j] = var[idx++];
}
}
}
return;
}
void moveF() { // F+
int var[13];
memset(var,0,sizeof(var));
int idx = 1;
int faces[] = {1,6,3,5};
for(int i=0;i<4;++i) {
int face = faces[i];
for(int j=1;j<=3;++j) {
if(face==1) {
var[idx++] = cube[face][3][j];
} else if(face==6) {
var[idx++] = cube[face][j][1];
} else if(face==3) {
var[idx++] = cube[face][1][4-j];
} else if(face==5) {
var[idx++] = cube[face][4-j][3];
}
}
}
rotate(var+1,var+10,var+13);
idx = 1;
for(int i=0;i<4;++i) {
int face = faces[i];
for(int j=1;j<=3;++j) {
if(face==1) {
cube[face][3][j] = var[idx++];
} else if(face==6) {
cube[face][j][1] = var[idx++];
} else if(face==3) {
cube[face][1][4-j] = var[idx++];
} else if(face==5) {
cube[face][4-j][3] = var[idx++];
}
}
}
return;
}
void moveB() { // B-
int var[13];
memset(var,0,sizeof(var));
int idx = 1;
int faces[] = {1,6,3,5};
for(int i=0;i<4;++i) {
int face = faces[i];
for(int j=1;j<=3;++j) {
if(face==1) {
var[idx++] = cube[face][1][j];
} else if(face==6) {
var[idx++] = cube[face][j][3];
} else if(face==3) {
var[idx++] = cube[face][3][4-j];
} else if(face==5) {
var[idx++] = cube[face][4-j][1];
}
}
}
rotate(var+1,var+10,var+13);
idx = 1;
for(int i=0;i<4;++i) {
int face = faces[i];
for(int j=1;j<=3;++j) {
if(face==1) {
cube[face][1][j] = var[idx++];
} else if(face==6) {
cube[face][j][3] = var[idx++];
} else if(face==3) {
cube[face][3][4-j] = var[idx++];
} else if(face==5) {
cube[face][4-j][1] = var[idx++];
}
}
}
return;
}
void move(char f, int d) {
// L,R : 1,2,3,4 (U,F,D,B)
// L+,R- : 1->2->3->4->1
// L-,R+ : 1->4->3->2->1
// U,D : 2,5,4,6 (F,L,B,R)
// U+,D- : 4->6->2->5->4
// U-,D+ : 4->5->2->6->4
// F,B : 1,6,3,5 (U,R,D,L)
// F+,B- : 1->6->3->5->1
// F-,B+ : 1->5->3->6->1
if(f=='L') {
if(d > 0) {
moveL();
matRotation(5,d);
} else if(d==0) {
for(int i=0;i<3;++i)
moveL();
matRotation(5,d);
}
} else if(f=='R') {
if(d > 0) {
for(int i=0;i<3;++i)
moveR();
matRotation(6,d);
} else if(d==0) {
moveR();
matRotation(6,d);
}
} else if(f=='U') {
if(d > 0) {
moveU();
matRotation(1,d);
} else if(d==0) {
for(int i=0;i<3;++i)
moveU();
matRotation(1,d);
}
} else if(f=='D') {
if(d > 0) {
for(int i=0;i<3;++i)
moveD();
matRotation(3,d);
} else if(d==0) {
moveD();
matRotation(3,d);
}
} else if(f=='F') {
if(d > 0) {
moveF();
matRotation(2,d);
} else if(d==0) {
for(int i=0;i<3;++i)
moveF();
matRotation(2,d);
}
} else if(f=='B') {
if(d > 0) {
for(int i=0;i<3;++i)
moveB();
matRotation(4,d);
} else if(d==0) {
moveB();
matRotation(4,d);
}
}
}
int main(void) {
// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
initCube();
for(int i=0;i<n;++i) {
scanf("%s", r);
char face = r[0];
int d = '-' - r[1]; // 2: '+', 0: '-'
move(face, d);
}
showFace(1); // show the top face
}
return 0;
}코드가 매우 길기 때문에 잘 쓴 코드라고 할 수는 없지만, 부분 부분 잘 나뉘어 있기 때문에 나중에 다시 볼 때 기억해내기 수월할 수 있을 것 같다.
실행 결과
조금씩 나아지는 중입니다!