일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 정규표현식
- Chunk
- nodejs
- update
- REACT
- REACTJS
- log_bin
- Node
- Express
- JavaScript
- 퀵소트
- upgrade
- Effective Java
- Effective Java 3/e
- Regular expression
- npm
- MySQL
- eslint
- Spring Batch
- spring
- current_date
- log4j2
- regex
- spring cloud
- mysql 5.5
- Webpack
- expire_logs_days
- migration
- git
- java
- Today
- Total
내 세상
[Algorithm] 백준 5373번 큐빙 본문
백준 5373번 큐빙
https://www.acmicpc.net/problem/5373
이 문제에서도 어김없이 패턴을 찾는 문제인데, 매우 귀찮고 어렵다.
큐브의 특정면을 바라볼 때, 시계 또는 반시계 방향으로 돌릴 수 있다.
그런데, 이 과정을 진행할 때 인접한 면들의 3X3의 각 좌표의 위치가 뒤죽박죽이 되기 때문에 매우 모니터 파괴 충동이 듬.
문제풀이
1. 큐브에는 초기에 지정된 색상이 있다.
방향 | Input | color / ouput |
위쪽 |
U - Upper |
White |
아래쪽 |
B - Bottom |
Yellow |
앞쪽 |
F - Front |
Red |
뒤쪽 |
B - Back |
Orange |
왼쪽 |
L - Left |
Green |
오른쪽 |
R - Right | Blue |
2. input으로 주어진 만큼 큐브를 회전시킨 후 위쪽(U-Upper)면의 색상을 출력한다. (띄어쓰기 없이)
열받는 포인트
1. 각 면의 3x3을 어떤 형태로 잡아도 돌리는 과정에서 조금씩 좌표 계산이 꼬이게 됨.
2. 큰 규칙이 있는데, 자꾸 작은 규칙부터 하나씩 차근차근 보여서 계속해서 문제가 발생함.
3. 공간지각능력이 매우 뛰어나야 하나, 몸이 따라오질 못함.
4. 회전시킬 때, 인접한 면도 색상이 변하게 되지만 회전시키는 본인의 색상도 돌아가야 함.
꿀팁
딱 봐도 느낌이 오겠지만, 왼쪽-오른쪽, 위쪽-아래쪽, 앞쪽-뒤쪽 등 각각 회전시켰을 때의 공식이 일부 일치되는 부분이 있음.
요거를 catch해서 잡아야 하는데, 한 단면을 돌리는 거에 대해서만 공식이 보이기 때문에 무작정 그것만보고 불나방 마냥 달려듬.
마치 나처럼...
위에 보이는 그림처럼 우선 각 면을 나의 상상속에 저장하고, 각 보이는 면의 왼쪽 위를 (0,0) 오른쪽 아래를 (2,2)로 정하고 전투에 돌입함.
한 면을 돌릴 때,
예를 들어 UPPER를 시계 방향으로 돌린다면, RIGHT -> FRONT -> LEFT -> BACK -> RIGHT 로 값이 변경된다.
반대로 반시계 방향으로 돌린다면, RIGHT -> BACK -> LEFT -> FRONT -> RIGHT 로 값이 변경된다.
즉 차이는 위의 순서 기준으로 2, 4번째가 서로 변경된다는 것임.
그리고 이제 더 크게 본다면, UPPER와 BOTTOM을 각각 시계 방향으로 돌린다 하면
각각을 시계 방향으로 돌리게 되더라도 실제로 회전을 시킬 때 내가 해당 면을 직시하고 있는 상황에서 회전시키는 것이기 때문에,
UPPER는 시계 방향으로 돌고, BOTTOM은 반시계 방향(UPPER를 기준으로 봤을 때)으로 돌게 된다.
이 말인 즉은 UPPER에서 시계 방향으로 회전하는 공식을 BOTTOM의 반시계 방향으로 회전하는 공식으로 쓸 수 있다는 것이다!! 위의 대사가 돌린 번역기를 돌린 외국인 같지만 외국인 아닙니다
하지만, UPPER를 돌릴 때 인접한 면의 UPPER에 인접한 친구들이 회전한다면 BOTTOM을 돌릴 때는 인접한 면의 BOTTOM에 인접한 친구들이 회전한다!
즉 UPPER를 돌릴 때 인접한 면의 첫번째 행의 값이 서로 변경된다면, BOTTOM을 돌릴 때는 인접한 면의 마지막 행(3행)의 값이 서로 변경된다는 말임.
방법을 알았기 때문에 코드는 정리되지 않는 순수 스레기 코드 입니다. 제가 생각한 것에서 한발 더 나아가는 방법이 있을 수도 있고, 더 좋은 방법이 있을 수 있지만 저는 머리가 아파서 이만하렵니다.
수고하세요
-------------------------------
추가))))) 19.3.10
너무 바보같이 쓴말들이 많아서 다시 한번 요약을 하자면,
1. 어떤 면이든 회전시킬 때, 시계/반시계 방향에 따라 식을 바꾸는 규칙이 있음.
2. UPPER/BOTTOM, LEFT/RIGHT, FRONT/BACK 등 마주 보고 있는 면은 서로 이동하는 식을 공유해서 쓸 수 있음.
물론 일부 변경이 필요함.
화이팅
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 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 | #include <iostream> #include <vector> #include <stdio.h> using namespace std; char cube[6][3][3]; char result[7] = { ' ','w', 'y', 'r', 'o', 'b', 'g' }; void initMap() { for (int k = 0; k < 6; k++) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { cube[k][i][j] = result[k + 1]; } } } } int main() { int T, N; cin >> T; for (int t = 1; t <= T; t++) { initMap(); cin >> N; char side, dir; for (int i = 0; i < N; i++) { cin >> side >> dir; if (side == 'U') { if (dir == '+') { int copy_cube[3][3]; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { copy_cube[j][k] = cube[0][j][k]; } } cube[0][0][2] = copy_cube[0][0]; cube[0][1][2] = copy_cube[0][1]; cube[0][2][2] = copy_cube[0][2]; cube[0][0][1] = copy_cube[1][0]; cube[0][2][1] = copy_cube[1][2]; cube[0][0][0] = copy_cube[2][0]; cube[0][1][0] = copy_cube[2][1]; cube[0][2][0] = copy_cube[2][2]; int temp[3]; temp[0] = cube[4][0][0]; temp[1] = cube[4][1][0]; temp[2] = cube[4][2][0]; for (int k = 0; k < 3; k++) cube[4][k][0] = cube[3][2][k]; for (int k = 0; k < 3; k++) cube[3][2][k] = cube[5][2 - k][2]; for (int k = 0; k < 3; k++) cube[5][2 - k][2] = cube[2][0][2 - k]; for (int k = 0; k < 3; k++) cube[2][0][2 - k] = temp[k]; } else { int copy_cube[3][3]; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { copy_cube[j][k] = cube[0][j][k]; } } cube[0][2][0] = copy_cube[0][0]; cube[0][1][0] = copy_cube[0][1]; cube[0][0][0] = copy_cube[0][2]; cube[0][2][1] = copy_cube[1][0]; cube[0][0][1] = copy_cube[1][2]; cube[0][2][2] = copy_cube[2][0]; cube[0][1][2] = copy_cube[2][1]; cube[0][0][2] = copy_cube[2][2]; int temp[3]; temp[0] = cube[4][0][0]; temp[1] = cube[4][1][0]; temp[2] = cube[4][2][0]; for (int k = 0; k < 3; k++) cube[4][k][0] = cube[2][0][2 - k]; for (int k = 0; k < 3; k++) cube[2][0][2 - k] = cube[5][2 - k][2]; for (int k = 0; k < 3; k++) cube[5][2 - k][2] = cube[3][2][k]; for (int k = 0; k < 3; k++) cube[3][2][k] = temp[k]; } } else if (side == 'D') { if (dir == '-') { int copy_cube[3][3]; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { copy_cube[j][k] = cube[1][j][k]; } } cube[1][2][0] = copy_cube[0][0]; cube[1][1][0] = copy_cube[0][1]; cube[1][0][0] = copy_cube[0][2]; cube[1][2][1] = copy_cube[1][0]; cube[1][0][1] = copy_cube[1][2]; cube[1][2][2] = copy_cube[2][0]; cube[1][1][2] = copy_cube[2][1]; cube[1][0][2] = copy_cube[2][2]; int temp[3]; temp[0] = cube[4][0][2]; temp[1] = cube[4][1][2]; temp[2] = cube[4][2][2]; for (int k = 0; k < 3; k++) cube[4][k][2] = cube[3][0][k]; for (int k = 0; k < 3; k++) cube[3][0][k] = cube[5][2 - k][0]; for (int k = 0; k < 3; k++) cube[5][2 - k][0] = cube[2][2][2 - k]; for (int k = 0; k < 3; k++) cube[2][2][2 - k] = temp[k]; } else { int copy_cube[3][3]; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { copy_cube[j][k] = cube[1][j][k]; } } cube[1][0][2] = copy_cube[0][0]; cube[1][1][2] = copy_cube[0][1]; cube[1][2][2] = copy_cube[0][2]; cube[1][0][1] = copy_cube[1][0]; cube[1][2][1] = copy_cube[1][2]; cube[1][0][0] = copy_cube[2][0]; cube[1][1][0] = copy_cube[2][1]; cube[1][2][0] = copy_cube[2][2]; int temp[3]; temp[0] = cube[4][0][2]; temp[1] = cube[4][1][2]; temp[2] = cube[4][2][2]; for (int k = 0; k < 3; k++) cube[4][k][2] = cube[2][2][2 - k]; for (int k = 0; k < 3; k++) cube[2][2][2 - k] = cube[5][2 - k][0]; for (int k = 0; k < 3; k++) cube[5][2 - k][0] = cube[3][0][k]; for (int k = 0; k < 3; k++) cube[3][0][k] = temp[k]; } } else if (side == 'F') { if (dir == '+') { int copy_cube[3][3]; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { copy_cube[j][k] = cube[2][j][k]; } } cube[2][0][2] = copy_cube[0][0]; cube[2][1][2] = copy_cube[0][1]; cube[2][2][2] = copy_cube[0][2]; cube[2][0][1] = copy_cube[1][0]; cube[2][2][1] = copy_cube[1][2]; cube[2][0][0] = copy_cube[2][0]; cube[2][1][0] = copy_cube[2][1]; cube[2][2][0] = copy_cube[2][2]; int temp[3]; temp[0] = cube[0][2][0]; temp[1] = cube[0][2][1]; temp[2] = cube[0][2][2]; for (int k = 0; k < 3; k++) cube[0][2][k] = cube[5][2][k]; for (int k = 0; k < 3; k++) cube[5][2][k] = cube[1][2][k]; for (int k = 0; k < 3; k++) cube[1][2][k] = cube[4][2][k]; for (int k = 0; k < 3; k++) cube[4][2][k] = temp[k]; } else { int copy_cube[3][3]; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { copy_cube[j][k] = cube[2][j][k]; } } cube[2][2][0] = copy_cube[0][0]; cube[2][1][0] = copy_cube[0][1]; cube[2][0][0] = copy_cube[0][2]; cube[2][2][1] = copy_cube[1][0]; cube[2][0][1] = copy_cube[1][2]; cube[2][2][2] = copy_cube[2][0]; cube[2][1][2] = copy_cube[2][1]; cube[2][0][2] = copy_cube[2][2]; int temp[3]; temp[0] = cube[0][2][0]; temp[1] = cube[0][2][1]; temp[2] = cube[0][2][2]; for (int k = 0; k < 3; k++) cube[0][2][k] = cube[4][2][k]; for (int k = 0; k < 3; k++) cube[4][2][k] = cube[1][2][k]; for (int k = 0; k < 3; k++) cube[1][2][k] = cube[5][2][k]; for (int k = 0; k < 3; k++) cube[5][2][k] = temp[k]; } } else if (side == 'B') { if (dir == '+') { int copy_cube[3][3]; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { copy_cube[j][k] = cube[3][j][k]; } } cube[3][0][2] = copy_cube[0][0]; cube[3][1][2] = copy_cube[0][1]; cube[3][2][2] = copy_cube[0][2]; cube[3][0][1] = copy_cube[1][0]; cube[3][2][1] = copy_cube[1][2]; cube[3][0][0] = copy_cube[2][0]; cube[3][1][0] = copy_cube[2][1]; cube[3][2][0] = copy_cube[2][2]; int temp[3]; temp[0] = cube[0][0][0]; temp[1] = cube[0][0][1]; temp[2] = cube[0][0][2]; for (int k = 0; k < 3; k++) cube[0][0][k] = cube[4][0][k]; for (int k = 0; k < 3; k++) cube[4][0][k] = cube[1][0][k]; for (int k = 0; k < 3; k++) cube[1][0][k] = cube[5][0][k]; for (int k = 0; k < 3; k++) cube[5][0][k] = temp[k]; } else { int copy_cube[3][3]; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { copy_cube[j][k] = cube[3][j][k]; } } cube[3][2][0] = copy_cube[0][0]; cube[3][1][0] = copy_cube[0][1]; cube[3][0][0] = copy_cube[0][2]; cube[3][2][1] = copy_cube[1][0]; cube[3][0][1] = copy_cube[1][2]; cube[3][2][2] = copy_cube[2][0]; cube[3][1][2] = copy_cube[2][1]; cube[3][0][2] = copy_cube[2][2]; int temp[3]; temp[0] = cube[0][0][0]; temp[1] = cube[0][0][1]; temp[2] = cube[0][0][2]; for (int k = 0; k < 3; k++) cube[0][0][k] = cube[5][0][k]; for (int k = 0; k < 3; k++) cube[5][0][k] = cube[1][0][k]; for (int k = 0; k < 3; k++) cube[1][0][k] = cube[4][0][k]; for (int k = 0; k < 3; k++) cube[4][0][k] = temp[k]; } } else if (side == 'L') { //0 위 1 아래 2 앞 3 뒤 4 오 5 왼 if (dir == '+') { int copy_cube[3][3]; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { copy_cube[j][k] = cube[5][j][k]; } } cube[5][0][2] = copy_cube[0][0]; cube[5][1][2] = copy_cube[0][1]; cube[5][2][2] = copy_cube[0][2]; cube[5][0][1] = copy_cube[1][0]; cube[5][2][1] = copy_cube[1][2]; cube[5][0][0] = copy_cube[2][0]; cube[5][1][0] = copy_cube[2][1]; cube[5][2][0] = copy_cube[2][2]; int temp[3]; temp[0] = cube[0][0][0]; temp[1] = cube[0][1][0]; temp[2] = cube[0][2][0]; for (int k = 0; k < 3; k++) cube[0][k][0] = cube[3][k][0]; for (int k = 0; k < 3; k++) cube[3][k][0] = cube[1][2 - k][2]; for (int k = 0; k < 3; k++) cube[1][2 - k][2] = cube[2][k][0]; for (int k = 0; k < 3; k++) cube[2][k][0] = temp[k]; } else { int copy_cube[3][3]; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { copy_cube[j][k] = cube[5][j][k]; } } cube[5][2][0] = copy_cube[0][0]; cube[5][1][0] = copy_cube[0][1]; cube[5][0][0] = copy_cube[0][2]; cube[5][2][1] = copy_cube[1][0]; cube[5][0][1] = copy_cube[1][2]; cube[5][2][2] = copy_cube[2][0]; cube[5][1][2] = copy_cube[2][1]; cube[5][0][2] = copy_cube[2][2]; int temp[3]; temp[0] = cube[0][0][0]; temp[1] = cube[0][1][0]; temp[2] = cube[0][2][0]; for (int k = 0; k < 3; k++) cube[0][k][0] = cube[2][k][0]; for (int k = 0; k < 3; k++) cube[2][k][0] = cube[1][2 - k][2]; for (int k = 0; k < 3; k++) cube[1][2 - k][2] = cube[3][k][0]; for (int k = 0; k < 3; k++) cube[3][k][0] = temp[k]; } } else if (side == 'R') { if (dir == '+') { int copy_cube[3][3]; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { copy_cube[j][k] = cube[4][j][k]; } } cube[4][0][2] = copy_cube[0][0]; cube[4][1][2] = copy_cube[0][1]; cube[4][2][2] = copy_cube[0][2]; cube[4][0][1] = copy_cube[1][0]; cube[4][2][1] = copy_cube[1][2]; cube[4][0][0] = copy_cube[2][0]; cube[4][1][0] = copy_cube[2][1]; cube[4][2][0] = copy_cube[2][2]; int temp[3]; temp[0] = cube[0][0][2]; temp[1] = cube[0][1][2]; temp[2] = cube[0][2][2]; for (int k = 0; k < 3; k++) cube[0][k][2] = cube[2][k][2]; for (int k = 0; k < 3; k++) cube[2][k][2] = cube[1][2 - k][0]; for (int k = 0; k < 3; k++) cube[1][2 - k][0] = cube[3][k][2]; for (int k = 0; k < 3; k++) cube[3][k][2] = temp[k]; } else { int copy_cube[3][3]; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { copy_cube[j][k] = cube[4][j][k]; } } cube[4][2][0] = copy_cube[0][0]; cube[4][1][0] = copy_cube[0][1]; cube[4][0][0] = copy_cube[0][2]; cube[4][2][1] = copy_cube[1][0]; cube[4][0][1] = copy_cube[1][2]; cube[4][2][2] = copy_cube[2][0]; cube[4][1][2] = copy_cube[2][1]; cube[4][0][2] = copy_cube[2][2]; int temp[3]; temp[0] = cube[0][0][2]; temp[1] = cube[0][1][2]; temp[2] = cube[0][2][2]; for (int k = 0; k < 3; k++) cube[0][k][2] = cube[3][k][2]; for (int k = 0; k < 3; k++) cube[3][k][2] = cube[1][2 - k][0]; for (int k = 0; k < 3; k++) cube[1][2 - k][0] = cube[2][k][2]; for (int k = 0; k < 3; k++) cube[2][k][2] = temp[k]; } } } for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { cout << cube[0][i][j]; } cout << endl; } } return 0; } | cs |
'Coding > Algorithms' 카테고리의 다른 글
[Algorithm] 백준 14501번 퇴사 (1) | 2019.03.17 |
---|---|
[Algorithm] 백준 15686번 치킨 배달 (0) | 2019.03.17 |
[Algorithm] 백준 14502번 연구소 (0) | 2019.02.21 |
[Algorithm] 백준 10951번 A+B-4 (0) | 2019.02.21 |
[Algorithm] 백준 16235번 나무 재테크 (0) | 2019.02.21 |