[Baekjoon] 5373 – 큐빙

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

📖 문제 이해하기

이 문제는 루빅스 큐브의 회전 동작을 정확히 시뮬레이션하는 것입니다. 우리에게는 완전히 풀린 상태의 3×3×3 루빅스 큐브가 주어지고, 일련의 회전 명령어들을 순서대로 적용한 후 최종적으로 윗면의 색상 배치를 출력해야 합니다.

초기 상태에서 각 면의 색상은 다음과 같이 정해져 있습니다. 윗면(U)은 흰색(w), 아랫면(D)은 노란색(y), 앞면(F)은 빨간색(r), 뒷면(B)은 오렌지색(o), 왼쪽면(L)은 초록색(g), 오른쪽면(R)은 파란색(b)입니다. 각 회전 명령어는 면을 나타내는 문자(U, D, F, B, L, R)와 방향을 나타내는 문자(+ 또는 -)로 구성됩니다. 여기서 +는 해당 면을 바라봤을 때 시계 방향, -는 반시계 방향 회전을 의미합니다.

예를 들어, L+ 명령어는 왼쪽 면을 시계 방향으로 90도 회전시키는 것이고, U-는 윗면을 반시계 방향으로 90도 회전시키는 것입니다. 이러한 회전들이 연속적으로 적용된 후, 우리는 윗면의 최종 색상 배치를 3×3 격자 형태로 출력해야 합니다.

🧠 첫 번째 접근과 그 한계

루빅스 큐브 문제를 처음 접하면, 가장 직관적인 접근법은 각 작은 정육면체(큐빛)를 개별 객체로 모델링하는 것입니다. 각 큐빛이 현재 어느 위치에 있는지, 어떤 방향으로 배치되어 있는지를 추적하면서 회전 시마다 이들의 위치와 방향을 업데이트하는 방식입니다.

하지만 이 접근법은 여러 가지 복잡성을 내포하고 있습니다. 먼저 각 큐빛의 3차원 좌표와 방향(orientation)을 정확히 추적해야 하고, 회전 시마다 복잡한 3차원 변환 행렬을 적용해야 합니다. 더 중요한 것은, 이 방법으로는 코드가 매우 길어지고 디버깅이 어려워진다는 점입니다. 특히 각 회전이 27개의 작은 큐빛에 어떤 영향을 미치는지 일일이 계산하고 관리하는 것은 실수를 유발하기 쉽습니다.

또 다른 문제는 성능입니다. 각 회전마다 많은 큐빛들의 상태를 업데이트해야 하므로, 회전 횟수가 많아질수록 계산량이 크게 늘어납니다. 이 문제에서는 최대 1000번의 회전이 가능하므로, 비효율적인 구현은 시간 초과를 일으킬 수 있습니다.

💡 핵심 아이디어: 면 중심의 모델링

효과적인 해결책은 루빅스 큐브를 6개의 개별 면으로 나누어 생각하는 것입니다. 각 면을 3×3 배열로 표현하고, 회전 시마다 해당 면 자체의 회전과 인접한 면들 간의 색상 교환을 동시에 처리하는 방식입니다.

이 접근법의 핵심 통찰은 루빅스 큐브의 회전이 본질적으로 두 가지 독립적인 동작으로 구성된다는 것입니다. 첫째, 회전되는 면 자체가 시계방향 또는 반시계방향으로 90도 회전합니다. 둘째, 그 면과 인접한 네 개 면의 특정 부분들이 순환적으로 색상을 교환합니다. 예를 들어 왼쪽 면을 시계방향으로 회전시키면, 앞면의 왼쪽 열, 윗면의 왼쪽 열, 뒷면의 왼쪽 열, 아랫면의 왼쪽 열이 순환적으로 색상을 교환합니다.

이러한 패턴을 파악하면, 각 회전에 대해 정확히 어떤 위치의 색상들이 어떤 순서로 이동하는지 미리 계산해 둘 수 있습니다. 이는 룰 기반의 시뮬레이션이 되어, 복잡한 3차원 계산 없이도 정확한 결과를 얻을 수 있게 해줍니다.

📘 시뮬레이션 기반 알고리즘에 대하여
시뮬레이션 기반 알고리즘은 복잡한 시스템의 동작을 단순한 규칙들의 조합으로 모델링하는 접근법입니다. 각 규칙이 정확하게 구현되면, 전체 시스템의 동작을 정밀하게 재현할 수 있습니다. 루빅스 큐브와 같은 물리적 퍼즐을 다룰 때 특히 유용한데, 실제 움직임의 패턴을 코드로 직접 번역할 수 있기 때문입니다.

🔍 알고리즘 동작 과정

구체적인 예시로 L+ (왼쪽 면 시계방향 회전) 명령어가 어떻게 처리되는지 살펴보겠습니다. 초기 상태에서는 모든 면이 단색으로 채워져 있습니다.

회전 전 상태에서 각 면의 색상을 확인해보면, 앞면(F)의 왼쪽 열은 모두 빨간색(r), 윗면(U)의 왼쪽 열은 모두 흰색(w), 뒷면(B)의 왼쪽 열은 모두 오렌지색(o), 아랫면(D)의 왼쪽 열은 모두 노란색(y)입니다. L+ 회전이 수행되면, 먼저 왼쪽 면 자체가 시계방향으로 90도 회전합니다. 이는 3×3 배열의 원소들이 특정 패턴으로 위치를 바꾸는 것으로 구현됩니다.

동시에 인접한 네 면의 왼쪽 열들이 순환 이동합니다. 구체적으로, 앞면의 왼쪽 열(빨간색)이 윗면의 왼쪽 열 위치로, 윗면의 왼쪽 열(흰색)이 뒷면의 왼쪽 열 위치로, 뒷면의 왼쪽 열(오렌지색)이 아랫면의 왼쪽 열 위치로, 아랫면의 왼쪽 열(노란색)이 앞면의 왼쪽 열 위치로 이동합니다.

이제 F- (앞면 반시계방향 회전)을 추가로 수행한다고 가정해봅시다. 앞면 자체가 반시계방향으로 회전하고, 동시에 윗면의 아래쪽 행, 오른쪽 면의 왼쪽 열, 아랫면의 위쪽 행, 왼쪽 면의 오른쪽 열이 순환 이동합니다. 이때 각 부분의 이동 방향과 순서를 정확히 추적해야 올바른 결과를 얻을 수 있습니다.

💻 소스 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX_N 1000000

<em>// 각 면을 나타내는 3x3 배열들</em>
<em>// U: 윗면, D: 아랫면, R: 오른쪽면, L: 왼쪽면, F: 앞면, B: 뒷면</em>
char U[9], D[9], R[9], L[9], F[9], B[9];

<em>// 큐브를 초기 상태로 리셋하는 함수</em>
<em>// 각 면을 해당하는 색상으로 균일하게 채움</em>
void reset() {
   for (int i = 0; i < 9; ++i) U[i] = 'w';  <em>// 윗면: 흰색</em>
   for (int i = 0; i < 9; ++i) D[i] = 'y';  <em>// 아랫면: 노란색</em>
   for (int i = 0; i < 9; ++i) F[i] = 'r';  <em>// 앞면: 빨간색</em>
   for (int i = 0; i < 9; ++i) B[i] = 'o';  <em>// 뒷면: 오렌지색</em>
   for (int i = 0; i < 9; ++i) L[i] = 'g';  <em>// 왼쪽면: 초록색</em>
   for (int i = 0; i < 9; ++i) R[i] = 'b';  <em>// 오른쪽면: 파란색</em>
}

<em>// 특정 면을 90도 회전시키는 함수</em>
<em>// 3x3 배열에서 시계방향/반시계방향 회전 패턴을 구현</em>
void rotatePage(char* A, char dir) {
   if (dir == '-') {  <em>// 반시계방향 회전</em>
      <em>// 모서리 4개 위치 순환: 0->2->8->6->0</em>
      char tmp = A[0];
      A[0] = A[2];
      A[2] = A[8];
      A[8] = A[6];
      A[6] = tmp;
      <em>// 변 중앙 4개 위치 순환: 1->5->7->3->1</em>
      tmp = A[1];
      A[1] = A[5];
      A[5] = A[7];
      A[7] = A[3];
      A[3] = tmp;
   } else {  <em>// 시계방향 회전</em>
      <em>// 모서리 4개 위치 순환: 0->6->8->2->0</em>
      char tmp = A[0];
      A[0] = A[6];
      A[6] = A[8];
      A[8] = A[2];
      A[2] = tmp;
      <em>// 변 중앙 4개 위치 순환: 1->3->7->5->1</em>
      tmp = A[1];
      A[1] = A[3];
      A[3] = A[7];
      A[7] = A[5];
      A[5] = tmp;
   }
}

<em>// 왼쪽 면 회전 함수</em>
<em>// 왼쪽 면 자체 회전 + 인접한 4개 면의 왼쪽 열 순환</em>
void rotateLeft(char dir) {
   int pos[3] = {0,3,6};  <em>// 각 면에서 왼쪽 열에 해당하는 인덱스들</em>
   char temp[9];
   <em>// 현재 앞면의 왼쪽 열 임시 저장</em>
   for (auto & p:pos) temp[p] = F[p];
   
   if (dir == '-') {  <em>// 반시계방향: F->D->B->U->F 순환</em>
      for (auto & p:pos) F[p] = D[p];
      for (auto & p:pos) D[p] = B[p];
      for (auto & p:pos) B[p] = U[p];
      for (auto & p:pos) U[p] = temp[p];
   } else {  <em>// 시계방향: F->U->B->D->F 순환</em>
      for (auto & p:pos) F[p] = U[p];
      for (auto & p:pos) U[p] = B[p];
      for (auto & p:pos) B[p] = D[p];
      for (auto & p:pos) D[p] = temp[p];
   }
   rotatePage(L, dir);  <em>// 왼쪽 면 자체도 회전</em>
}

<em>// 오른쪽 면 회전 함수</em>
<em>// 왼쪽 면과 유사하지만 오른쪽 열(인덱스 2,5,8) 처리</em>
void rotateRight(char dir) {
   int pos[3] = {2,5,8};  <em>// 각 면에서 오른쪽 열에 해당하는 인덱스들</em>
   char temp[9];
   for (auto & p:pos) temp[p] = F[p];
   
   if (dir == '+') {  <em>// 시계방향: F->D->B->U->F 순환</em>
      for (auto & p:pos) F[p] = D[p];
      for (auto & p:pos) D[p] = B[p];
      for (auto & p:pos) B[p] = U[p];
      for (auto & p:pos) U[p] = temp[p];
   } else {  <em>// 반시계방향: F->U->B->D->F 순환</em>
      for (auto & p:pos) F[p] = U[p];
      for (auto & p:pos) U[p] = B[p];
      for (auto & p:pos) B[p] = D[p];
      for (auto & p:pos) D[p] = temp[p];
   }
   rotatePage(R, dir);
}

<em>// 윗면 회전 함수</em>
<em>// 윗면 자체 회전 + 앞,오른쪽,뒷,왼쪽 면의 윗쪽 행 순환</em>
void rotateUp(char dir) {
   int pos[3] = {0,1,2};  <em>// 각 면에서 윗쪽 행에 해당하는 인덱스들</em>
   char temp[9];
   for (auto & p:pos) temp[p] = F[p];
   
   if (dir == '+') {  <em>// 시계방향</em>
      <em>// 특별히 뒷면은 순서가 뒤바뀜 (8-p 사용)</em>
      for (auto & p:pos) F[p] = R[p];
      for (auto & p:pos) R[p] = B[8-p];
      for (auto & p:pos) B[8-p] = L[p];
      for (auto & p:pos) L[p] = temp[p];
   } else {  <em>// 반시계방향</em>
      for (auto & p:pos) F[p] = L[p];
      for (auto & p:pos) L[p] = B[8-p];
      for (auto & p:pos) B[8-p] = R[p];
      for (auto & p:pos) R[p] = temp[p];
   }
   rotatePage(U, dir);
}

<em>// 아랫면 회전 함수</em>
<em>// 윗면과 유사하지만 아래쪽 행(인덱스 6,7,8) 처리</em>
void rotateDown(char dir) {
   int pos[3] = {6,7,8};  <em>// 각 면에서 아래쪽 행에 해당하는 인덱스들</em>
   char temp[9];
   for (auto & p:pos) temp[p] = F[p];
   
   if (dir == '-') {  <em>// 반시계방향</em>
      for (auto & p:pos) F[p] = R[p];
      for (auto & p:pos) R[p] = B[8-p];
      for (auto & p:pos) B[8-p] = L[p];
      for (auto & p:pos) L[p] = temp[p];
   } else {  <em>// 시계방향</em>
      for (auto & p:pos) F[p] = L[p];
      for (auto & p:pos) L[p] = B[8-p];
      for (auto & p:pos) B[8-p] = R[p];
      for (auto & p:pos) R[p] = temp[p];
   }
   rotatePage(D, dir);
}

<em>// 앞면 회전 함수</em>
<em>// 앞면 자체 회전 + 윗,오른쪽,아래,왼쪽 면의 해당 부분 순환</em>
void rotateFront(char dir) {
   int pos[3] = {6,7,8};  <em>// 윗면에서 앞면과 인접한 부분 (아래쪽 행)</em>
   char temp[9];
   for (auto & p:pos) temp[p] = U[p];
   
   if (dir == '-') {  <em>// 반시계방향</em>
      <em>// 복잡한 인덱스 매핑: 각 면의 특정 위치들이 회전</em>
      U[6] = R[0], U[7] = R[3], U[8] = R[6];
      R[0] = D[2], R[3] = D[1], R[6] = D[0];
      D[0] = L[2], D[1] = L[5], D[2] = L[8];
      L[2] = temp[8], L[5] = temp[7], L[8] = temp[6];
   } else {  <em>// 시계방향</em>
      U[6] = L[8], U[7] = L[5], U[8] = L[2];
      L[8] = D[2], L[5] = D[1], L[2] = D[0];
      D[0] = R[6], D[1] = R[3], D[2] = R[0];
      R[6] = temp[8], R[3] = temp[7], R[0] = temp[6];
   }
   rotatePage(F, dir);
}

<em>// 뒷면 회전 함수</em>
<em>// 앞면과 유사하지만 다른 인덱스 매핑 사용</em>
void rotateBack(char dir) {
   int pos[3] = {0,1,2};  <em>// 윗면에서 뒷면과 인접한 부분 (위쪽 행)</em>
   char temp[9];
   for (auto & p:pos) temp[p] = U[p];
   
   if (dir == '+') {  <em>// 시계방향</em>
      U[0] = R[2], U[1] = R[5], U[2] = R[8];
      R[2] = D[8], R[5] = D[7], R[8] = D[6];
      D[8] = L[6], D[7] = L[3], D[6] = L[0];
      L[0] = temp[2], L[3] = temp[1], L[6] = temp[0];
   } else {  <em>// 반시계방향</em>
      U[0] = L[6], U[1] = L[3], U[2] = L[0];
      L[0] = D[6], L[3] = D[7], L[6] = D[8];
      D[6] = R[8], D[7] = R[5], D[8] = R[2];
      R[8] = temp[2], R[5] = temp[1], R[2] = temp[0];
   }
   rotatePage(B, dir);
}

<em>// 회전 명령어를 파싱하여 해당 함수 호출</em>
void action(char page, char dir) {
   switch(page) {
   case 'L':
      rotateLeft(dir);
      break;
   case 'R':
      rotateRight(dir);
      break;
   case 'U':
      rotateUp(dir);
      break;
   case 'D':
      rotateDown(dir);
      break;
   case 'F':
      rotateFront(dir);
      break;
   case 'B':
      rotateBack(dir);
      break;
   }
}

int main()
{
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int N, M;
   cin >> N;  <em>// 테스트 케이스 개수</em>

   string comm;
   for (int i = 0; i < N; ++i) {
      cin >> M;  <em>// 회전 횟수</em>
      reset();   <em>// 각 테스트 케이스마다 큐브를 초기 상태로 리셋</em>
      
      <em>// M번의 회전 명령어 처리</em>
      for (int j = 0; j < M; ++j) {
         cin >> comm;
         action(comm[0], comm[1]);  <em>// 첫 번째 문자: 면, 두 번째 문자: 방향</em>
      }
      
      <em>// 최종 윗면 상태 출력 (3x3 격자 형태)</em>
      for (int i = 0; i <3; ++i) {
         for (int j = 0; j < 3; ++j) {
            cout << U[i*3+j];
         }
         cout << "\n";
      }
   }

   return 0;
}

📌 핵심 포인트와 배운 점

이 문제를 통해 우리는 복잡한 3차원 시뮬레이션을 효과적으로 구현하는 방법을 배웠습니다. 가장 중요한 통찰은 물리적 객체의 움직임을 추상화하여 규칙 기반의 상태 변환으로 모델링할 수 있다는 것입니다.

루빅스 큐브의 각 회전은 정해진 패턴에 따라 색상들을 재배치하는 과정으로 이해할 수 있으며, 이러한 패턴들을 정확히 파악하고 코드로 구현하는 것이 핵심입니다. 특히 각 면의 회전과 인접 면들 간의 색상 교환이 독립적으로 일어나는 것이 아니라 동시에 발생한다는 점을 이해하는 것이 중요했습니다.

이 접근법은 다른 복잡한 시뮬레이션 문제에도 적용할 수 있는 일반적인 전략을 제공합니다. 시스템의 전체적인 동작을 작은 규칙들의 조합으로 분해하고, 각 규칙을 정확히 구현한 다음, 이들을 순차적으로 적용하여 최종 결과를 얻는 방식입니다.