반응형
알고리즘 분류 : 시뮬레이션
루믹스 큐브의 회전을 주어진 조건 그대로 구현하는 문제다. 큐브의 좌표를 적당히 설정해서 회전하면 된다. 번뜩이는 아이디어가 떠오르지 않아서 무식하게 구현했다. 배열 인덱스가 꼬이기 십상인지라, 상당히 번거롭고 귀찮은 문제다.
- 큐브를 적당히 고정해놓고 좌표를 설정한다.
- 각 면에 인덱스를 0~5까지 붙였다.
- 3차원 배열 cube의 인덱스는 [면 번호] [서브 사각형 X좌표] [서브 사각형 Y좌표] 이다.
- 각 면은 3*3의 서브 사각형으로 이루어져 있으며, 각 좌표는 (0,0)부터 (2,2)까지이다.
- 아래 그림에서 각 면에 있는 검은색 점은 (0,0)의 위치다.
- 각 면을 정면으로 바라보는 기준으로 회전을 시키면서 좌표의 변화를 업데이트해야 한다.
C++ 소스코드
#include <cstdio> int n; char a[3], temp[3], t[3][3]; char cube[6][3][3]; const char C[] = "wyrogb"; void copy(int d) { for (int i=0; i<3; i++) { for (int j=0; j<3; j++) { t[i][j] = cube[d][i][j]; } } } void cw(int d) { copy(d); cube[d][0][0] = t[2][0]; cube[d][0][1] = t[1][0]; cube[d][0][2] = t[0][0]; cube[d][1][0] = t[2][1]; cube[d][1][2] = t[0][1]; cube[d][2][0] = t[2][2]; cube[d][2][1] = t[1][2]; cube[d][2][2] = t[0][2]; } void ccw(int d) { copy(d); cube[d][0][0] = t[0][2]; cube[d][0][1] = t[1][2]; cube[d][0][2] = t[2][2]; cube[d][1][0] = t[0][1]; cube[d][1][2] = t[2][1]; cube[d][2][0] = t[0][0]; cube[d][2][1] = t[1][0]; cube[d][2][2] = t[2][0]; } void rotateU(int k) { for (int i=0; i<3; i++) temp[i] = cube[4][k][i]; for (int i=0; i<3; i++) cube[4][k][i] = cube[2][k][i]; for (int i=0; i<3; i++) cube[2][k][i] = cube[5][k][i]; for (int i=0; i<3; i++) cube[5][k][i] = cube[3][k][i]; for (int i=0; i<3; i++) cube[3][k][i] = temp[i]; } void rotateD(int k) { for (int i=0; i<3; i++) temp[i] = cube[4][k][i]; for (int i=0; i<3; i++) cube[4][k][i] = cube[3][k][i]; for (int i=0; i<3; i++) cube[3][k][i] = cube[5][k][i]; for (int i=0; i<3; i++) cube[5][k][i] = cube[2][k][i]; for (int i=0; i<3; i++) cube[2][k][i] = temp[i]; } void rotateF(int k) { int j = k == 0 ? 2 : 0; for (int i=0; i<3; i++) temp[i] = cube[0][k][i]; for (int i=0; i<3; i++) cube[0][k][i] = cube[4][2-i][k]; for (int i=0; i<3; i++) cube[4][i][k] = cube[1][j][i]; for (int i=0; i<3; i++) cube[1][j][i] = cube[5][2-i][j]; for (int i=0; i<3; i++) cube[5][i][j] = temp[i]; } void rotateB(int k) { int j = k == 0 ? 2 : 0; for (int i=0; i<3; i++) temp[i] = cube[0][k][i]; for (int i=0; i<3; i++) cube[0][k][i] = cube[5][i][j]; for (int i=0; i<3; i++) cube[5][i][j] = cube[1][j][2-i]; for (int i=0; i<3; i++) cube[1][j][i] = cube[4][i][k]; for (int i=0; i<3; i++) cube[4][i][k] = temp[2-i]; } void rotateL(int k) { int j = k == 0 ? 2 : 0; for (int i=0; i<3; i++) temp[i] = cube[0][i][k]; for (int i=0; i<3; i++) cube[0][i][k] = cube[3][2-i][j]; for (int i=0; i<3; i++) cube[3][i][j] = cube[1][2-i][k]; for (int i=0; i<3; i++) cube[1][i][k] = cube[2][i][k]; for (int i=0; i<3; i++) cube[2][i][k] = temp[i]; } void rotateR(int k) { int j = k == 0 ? 2 : 0; for (int i=0; i<3; i++) temp[i] = cube[0][i][k]; for (int i=0; i<3; i++) cube[0][i][k] = cube[2][i][k]; for (int i=0; i<3; i++) cube[2][i][k] = cube[1][i][k]; for (int i=0; i<3; i++) cube[1][i][k] = cube[3][2-i][j]; for (int i=0; i<3; i++) cube[3][i][j] = temp[2-i]; } void solve() { switch (a[0]) { case 'U': if (a[1] == '+') { cw(0); rotateU(0); } else { ccw(0); rotateD(0); } break; case 'D': if (a[1] == '-') { ccw(1); rotateU(2); } else { cw(1); rotateD(2); } break; case 'F': if (a[1] == '+') { cw(2); rotateF(2); } else { ccw(2); rotateB(2); } break; case 'B': if (a[1] == '-') { ccw(3); rotateF(0); } else { cw(3); rotateB(0); } break; case 'L': if (a[1] == '+') { cw(4); rotateL(0); } else { ccw(4); rotateR(0); } break; case 'R': if (a[1] == '-') { ccw(5); rotateL(2); } else { cw(5); rotateR(2); } break; default: break; } } int main() { int t; scanf("%d", &t); while (t--) { for (int i=0; i<6; i++) { for (int j=0; j<3; j++) { for (int k=0; k<3; k++) { cube[i][j][k] = C[i]; } } } scanf("%d", &n); for (int i=0; i<n; i++) { scanf("%s", a); solve(); } for (int i=0; i<3; i++) { for (int j=0; j<3; j++) { printf("%c", cube[0][i][j]); } printf("\n"); } } return 0; }
Python 3 소스코드
✓ 구현이 귀찮으므로 생략 (...)
참고
- 백준 온라인 저지 : BOJ 5373
반응형