알고리즘/시뮬레이션
[백준]큐빙
안잡아모찌
2019. 7. 29. 18:20
https://www.acmicpc.net/problem/5373
5373번: 큐빙
문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다. 이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란
www.acmicpc.net
극강의 시뮬레이션 문제다. 어떻게 해야겠다는 생각자체는 쉽지만 Shift가 워낙 많아서 꺼려지는 문제...
구현량이 워낙많기 때문에 인덱스 실수하기가 좋다..
일단 코드를 그나마 줄이기위해서는 시계, 반시계는 Cycle이므로 (시계*3 = 반시계) 라는 생각을 하면 조금이나마
줄일수 있다.
그리고 2차원 전개도로 나타내서 돌렸을때의 결과를 생각해 볼 수 있다. 주사위 전개도에 대한 약간의 이해필요
별다른 스킬같은건 없다...
그리고 계속 중첩되서 돌리는 건줄 알아서 좀 삽질했다..
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#include <iostream>
using namespace std;
/*시뮬시뮬
1.+시계, - 반시계
U0 U1 U2
U3 U4 U5
U6 U7 U8
ㅡㅡㅡㅡ
L0 L1 L2 | F0 F1 F2 | R0 R1 R2 | B0 B1 B2
L3 L4 L5 | F3 F4 F5 | R3 R4 R5 | B3 B4 B5
L6 L7 L8 | F6 F7 F8 | R6 R7 R8 | B6 B7 B8
ㅡㅡㅡㅡ
D0 D1 D2
D3 D4 D5
D6 D7 D8
*/
struct CUBE {
public:
char U[10] = { 'w','w', 'w', 'w', 'w', 'w', 'w', 'w', 'w' };
char D[10] = { 'y','y', 'y', 'y', 'y', 'y', 'y', 'y', 'y' };
char L[10] = { 'g','g', 'g', 'g', 'g', 'g', 'g', 'g', 'g' };
char R[10] = { 'b','b', 'b', 'b', 'b', 'b', 'b', 'b', 'b' };
char F[10] = { 'r','r', 'r', 'r', 'r', 'r', 'r', 'r', 'r' };
char B[10] = { 'o','o', 'o', 'o', 'o', 'o', 'o', 'o', 'o' };
CUBE() {};
};
CUBE c1;
int T, N;
void RotationUP() {
char tmp1[4];
tmp1[0] = c1.U[0]; tmp1[1] = c1.U[1]; tmp1[2] = c1.U[2];
c1.U[0] = c1.U[6]; c1.U[1] = c1.U[3]; c1.U[2] = c1.U[0];
c1.U[0] = c1.U[6]; c1.U[3] = c1.U[7]; c1.U[6] = c1.U[8];
c1.U[6] = c1.U[8]; c1.U[7] = c1.U[5]; c1.U[8] = c1.U[2];
c1.U[2] = tmp1[0]; c1.U[5] = tmp1[1]; c1.U[8] = tmp1[2];
char tmp2[4];
tmp2[0] = c1.B[2]; tmp2[1] = c1.B[1]; tmp2[2] = c1.B[0];
c1.B[2] = c1.L[2]; c1.B[1] = c1.L[1]; c1.B[0] = c1.L[0];
c1.L[0] = c1.F[0]; c1.L[1] = c1.F[1]; c1.L[2] = c1.F[2];
c1.F[0] = c1.R[0]; c1.F[1] = c1.R[1]; c1.F[2] = c1.R[2];
c1.R[0] = tmp2[2]; c1.R[1] = tmp2[1]; c1.R[2] = tmp2[0];
}
void RotationDOWN() {
char tmp1[7];
tmp1[0] = c1.D[0]; tmp1[1] = c1.D[1]; tmp1[2] = c1.D[2];
c1.D[0] = c1.D[6]; c1.D[1] = c1.D[3]; c1.D[2] = c1.D[0];
c1.D[0] = c1.D[6]; c1.D[3] = c1.D[7]; c1.D[6] = c1.D[8];
c1.D[6] = c1.D[8]; c1.D[7] = c1.D[5]; c1.D[8] = c1.D[2];
c1.D[2] = tmp1[0]; c1.D[5] = tmp1[1]; c1.D[8] = tmp1[2];
char tmp2[4];
tmp2[0] = c1.F[6]; tmp2[1] = c1.F[7]; tmp2[2] = c1.F[8];
c1.F[6] = c1.L[6]; c1.F[7] = c1.L[7]; c1.F[8] = c1.L[8];
c1.L[8] = c1.B[8]; c1.L[7] = c1.B[7]; c1.L[6] = c1.B[6];
c1.B[8] = c1.R[8]; c1.B[7] = c1.R[7]; c1.B[6] = c1.R[6];
c1.R[8] = tmp2[2]; c1.R[7] = tmp2[1]; c1.R[6] = tmp2[0];
}
void RotationLEFT() {
char tmp1[7];
tmp1[0] = c1.L[0]; tmp1[1] = c1.L[1]; tmp1[2] = c1.L[2];
c1.L[0] = c1.L[6]; c1.L[1] = c1.L[3]; c1.L[2] = c1.L[0];
c1.L[0] = c1.L[6]; c1.L[3] = c1.L[7]; c1.L[6] = c1.L[8];
c1.L[6] = c1.L[8]; c1.L[7] = c1.L[5]; c1.L[8] = c1.L[2];
c1.L[2] = tmp1[0]; c1.L[5] = tmp1[1]; c1.L[8] = tmp1[2];
char tmp2[4];
tmp2[0] = c1.U[0]; tmp2[1] = c1.U[3]; tmp2[2] = c1.U[6];
c1.U[0] = c1.B[8]; c1.U[3] = c1.B[5]; c1.U[6] = c1.B[2];
c1.B[2] = c1.D[6]; c1.B[5] = c1.D[3]; c1.B[8] = c1.D[0];
c1.D[6] = c1.F[6]; c1.D[3] = c1.F[3]; c1.D[0] = c1.F[0];
c1.F[0] = tmp2[0]; c1.F[3] = tmp2[1]; c1.F[6] = tmp2[2];
}
void RotationRIGHT() {
char tmp1[7];
tmp1[0] = c1.R[0]; tmp1[1] = c1.R[1]; tmp1[2] = c1.R[2];
c1.R[0] = c1.R[6]; c1.R[1] = c1.R[3]; c1.R[2] = c1.R[0];
c1.R[0] = c1.R[6]; c1.R[3] = c1.R[7]; c1.R[6] = c1.R[8];
c1.R[6] = c1.R[8]; c1.R[7] = c1.R[5]; c1.R[8] = c1.R[2];
c1.R[2] = tmp1[0]; c1.R[5] = tmp1[1]; c1.R[8] = tmp1[2];
char tmp2[4];
tmp2[0] = c1.U[8]; tmp2[1] = c1.U[5]; tmp2[2] = c1.U[2];
c1.U[8] = c1.F[8]; c1.U[5] = c1.F[5]; c1.U[2] = c1.F[2];
c1.F[2] = c1.D[2]; c1.F[5] = c1.D[5]; c1.F[8] = c1.D[8];
c1.D[2] = c1.B[6]; c1.D[5] = c1.B[3]; c1.D[8] = c1.B[0];
c1.B[0] = tmp2[0]; c1.B[3] = tmp2[1]; c1.B[6] = tmp2[2];
}
void RotationFRONT() {
char tmp1[7];
tmp1[0] = c1.F[0]; tmp1[1] = c1.F[1]; tmp1[2] = c1.F[2];
c1.F[0] = c1.F[6]; c1.F[1] = c1.F[3]; c1.F[2] = c1.F[0];
c1.F[0] = c1.F[6]; c1.F[3] = c1.F[7]; c1.F[6] = c1.F[8];
c1.F[6] = c1.F[8]; c1.F[7] = c1.F[5]; c1.F[8] = c1.F[2];
c1.F[2] = tmp1[0]; c1.F[5] = tmp1[1]; c1.F[8] = tmp1[2];
char tmp2[4];
tmp2[0] = c1.U[6]; tmp2[1] = c1.U[7]; tmp2[2] = c1.U[8];
c1.U[6] = c1.L[8]; c1.U[7] = c1.L[5]; c1.U[8] = c1.L[2];
c1.L[2] = c1.D[0]; c1.L[5] = c1.D[1]; c1.L[8] = c1.D[2];
c1.D[0] = c1.R[6]; c1.D[1] = c1.R[3]; c1.D[2] = c1.R[0];
c1.R[0] = tmp2[0]; c1.R[3] = tmp2[1]; c1.R[6] = tmp2[2];
}
void RotationBACK() {
char tmp1[7];
tmp1[0] = c1.B[0]; tmp1[1] = c1.B[1]; tmp1[2] = c1.B[2];
c1.B[0] = c1.B[6]; c1.B[1] = c1.B[3]; c1.B[2] = c1.B[0];
c1.B[0] = c1.B[6]; c1.B[3] = c1.B[7]; c1.B[6] = c1.B[8];
c1.B[6] = c1.B[8]; c1.B[7] = c1.B[5]; c1.B[8] = c1.B[2];
c1.B[2] = tmp1[0]; c1.B[5] = tmp1[1]; c1.B[8] = tmp1[2];
char tmp2[4];
tmp2[0] = c1.U[2]; tmp2[1] = c1.U[1]; tmp2[2] = c1.U[0];
c1.U[2] = c1.R[8]; c1.U[1] = c1.R[5]; c1.U[0] = c1.R[2];
c1.R[2] = c1.D[8]; c1.R[5] = c1.D[7]; c1.R[8] = c1.D[6];
c1.D[8] = c1.L[6]; c1.D[7] = c1.L[3]; c1.D[6] = c1.L[0];
c1.L[0] = tmp2[0]; c1.L[3] = tmp2[1]; c1.L[6] = tmp2[2];
}
void solve(char plane, char dir) {
if (plane == 'U') { RotationUP(); if (dir == '-') { RotationUP(); RotationUP(); } }
else if (plane == 'D') { RotationDOWN(); if (dir == '-') { RotationDOWN(); RotationDOWN(); } }
else if (plane == 'L') { RotationLEFT(); if (dir == '-') { RotationLEFT(); RotationLEFT(); } }
else if (plane == 'R') { RotationRIGHT(); if (dir == '-') { RotationRIGHT(); RotationRIGHT(); } }
else if (plane == 'F') { RotationFRONT(); if (dir == '-') { RotationFRONT(); RotationFRONT(); } }
else if (plane == 'B') { RotationBACK(); if (dir == '-') { RotationBACK(); RotationBACK(); } }
}
int main()
{
cin >> T;
for (int i = 0; i < T; i++) {
c1 = CUBE();
cin >> N;
char a[3];
for (int k = 0; k < N; k++) {
cin >> a;
solve(a[0], a[1]);
}
printf("%c%c%c\n%c%c%c\n%c%c%c\n", c1.U[0], c1.U[1], c1.U[2], c1.U[3], c1.U[4], c1.U[5], c1.U[6], c1.U[7], c1.U[8]);
}
return 0;
}
|
cs |