[백준 BOJ 5373] 큐빙 (Python 파이썬)

큐빙

플래티넘5, 구현, Simulation

제한 조건
시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	12347	4814	3276	38.275%

문제

루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다.

큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다.

이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란색, 앞 면은 빨간색, 뒷 면은 오렌지색, 왼쪽 면은 초록색, 오른쪽 면은 파란색이다.

루빅스 큐브를 돌린 방법이 순서대로 주어진다. 이때, 모두 돌린 다음에 가장 윗 면의 색상을 구하는 프로그램을 작성하시오.

위의 그림은 루빅스 큐브를 푼 그림이다. 왼쪽 면은 시계방향으로 조금 돌려져 있는 상태이다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다. 각 테스트 케이스는 다음과 같이 구성되어져 있다.

• 첫째 줄에 큐브를 돌린 횟수 n이 주어진다. (1 ≤ n ≤ 1000)
• 둘째 줄에는 큐브를 돌린 방법이 주어진다. 각 방법은 공백으로 구분되어져 있으며, 첫 번째 문자는 돌린 면이다. U: 윗 면, D: 아랫 면, F: 앞 면, B: 뒷 면, L: 왼쪽 면, R: 오른쪽 면이다. 두 번째 문자는 돌린 방향이다. +인 경우에는 시계 방향 (그 면을 바라봤을 때가 기준), -인 경우에는 반시계 방향이다.

출력

각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란색은 y, 빨간색은 r, 오렌지색은 o, 초록색은 g, 파란색은 b.

예제 입력 1

4
1
L-
2
F+ B+
4
U- D- L+ R+
10
L- U- L+ U- L- U- U- L+ U+ U+

예제 출력 1

rww
rww
rww
bbb
www
ggg
gwg
owr
bwb
gwo
www
rww

 

---

풀이

import sys
input = sys.stdin.readline

class Cubic:
    def __init__(self):
        self.cubic = {
            "U":[["w"]*3 for _ in range(3)], 
            "D":[["y"]*3 for _ in range(3)], 
            "F":[["r"]*3 for _ in range(3)], 
            "B":[["o"]*3 for _ in range(3)], 
            "L":[["g"]*3 for _ in range(3)], 
            "R":[["b"]*3 for _ in range(3)],
        }
        self.rot_info = {
            "U":{"B":0,     "R":180,    "F":180,    "L":180,},
            "D":{"F":0,     "R":0,      "B":180,    "L":0,},
            "F":{"U":0,     "R":270,    "D":180,    "L":90,},
            "B":{"D":0,     "R":90,     "U":180,    "L":270,},
            "L":{"U":270,   "F":270,    "D":270,    "B":270,},
            "R":{"U":90,    "B":90,     "D":90,     "F":90,},
        }

    def lot_surface(self, surface, degree=90):
        if degree == 90:
            self.cubic[surface] = [i[::-1] for i in zip(*self.cubic[surface])]
        elif degree == 180:
            self.cubic[surface] = [i[::-1] for i in self.cubic[surface]][::-1]
        elif degree == 270:
            self.cubic[surface] = [i for i in zip(*self.cubic[surface])][::-1]

    def process(self, rot_seq):
        tmp = self.cubic[rot_seq[3]].pop()
        for i in range(3,0,-1):
            l, r = rot_seq[i], rot_seq[i-1]
            self.cubic[l].append(self.cubic[r].pop())
        self.cubic[rot_seq[0]].append(tmp)

    def rot90(self, surface):
        surface_rot_info = self.rot_info[surface]
        for s, d in surface_rot_info.items():
            self.lot_surface(s,d)
        self.process(list(surface_rot_info.keys()))
        self.lot_surface(surface)
        for s, d in surface_rot_info.items():
            self.lot_surface(s, 360-d)

    def turn(self, surface, method):
        for _ in range(1 if method=="+" else 3):
            self.rot90(surface)

    def print(self, surface="U"):
        for l in self.cubic[surface]:
            print(*l, sep="")

if __name__=="__main__":
    n = int(input())
    for tc in range(n):
        _ = input()
        cubic = Cubic()
        for cmd in input().split():
            cubic.turn(*list(cmd))
        cubic.print()

 시간, 메모리 제한이 까다롭지 않아서 시키는 대로 잘 구현만 하면 됐지만, 3차원 공간의 큐브를 내 방식대로 이해하고 적용하는게 꽤 까다로운 문제였던 것 같다.

 구현이 까다로운 문제는 자기 입맛에 맞게 문제를 바꾸는 것이 중요하다고 생각한다. 이 문제의 경우 큐브를 보는 방향을 고정하고 큐브를 돌리는 과정을 최대한 간단히 구현하는 것이 문제 풀이에 성공하는데 큰 도움을 줬다.

(사실 시간복잡도 측면에서는 매우 비효율적인 풀이이다. 이번 문제는 조건이 널널해서 빠르고 쉽게 구현하는 것에 초점을 맞췄다.)

 

큐브 방향 고정

큐브는 3차원이다. 지능의 한계로 3차원 큐브가 돌아가는 과정을 머릿속으로 명확히 떠올리긴 힘들었다.

그래서 우선 도면을 떠올렸다.

 

모든 면의 상하좌우를 우측 도면과 동일하게 생각한다.

Front를 시계방향으로 돌리는 경우

1. Front의 모든 면은 시계방향으로 90도 회전한다.

2. Up의 가장 아래에 있는 줄은 Right의 좌측 줄로 이동한다.

3. Right의 좌측 줄은 Down의 최상단 줄로 이동한다.

4. Down의 최상단 줄은 Left의 우측 줄로 이동한다.

 

이를 코드로 구현할 때, index를 직접 지정해 주거나 연결리스트를 활용하는 방식으로 구현할 수 있다. 하지만 문제 조건이 어렵지 않아 몇가지 트릭을 활용할 수 있어 가장 간단한 방법으로 면을 구성했다. 면에 해당하는 2차원 배열의 열 인덱스는 위부터 아래로 0~2, 행은 좌부터 우로 0~2이다.

 

        self.cubic = {
            "U":[["w"]*3 for _ in range(3)], 
            "D":[["y"]*3 for _ in range(3)], 
            "F":[["r"]*3 for _ in range(3)], 
            "B":[["o"]*3 for _ in range(3)], 
            "L":[["g"]*3 for _ in range(3)], 
            "R":[["b"]*3 for _ in range(3)],
        }

표면 배열 단순화

어떤 한 면을 돌릴 때, 해당 면은 90도 혹은 270도 회전하게 된다. 어렵지 않은 면 회전 코드를 먼저 구현한다.

    def lot_surface(self, surface, degree=90):
        if degree == 90:
            self.cubic[surface] = [i[::-1] for i in zip(*self.cubic[surface])]
        elif degree == 180:
            self.cubic[surface] = [i[::-1] for i in self.cubic[surface]][::-1]
        elif degree == 270:
            self.cubic[surface] = [i for i in zip(*self.cubic[surface])][::-1]

이로써 면을 90, 180, 270도 회전하는 동작은 쉽게 활용이 가능하다.

 

이후, 인접한 4개의 면을 회전시켜야 한다.

 

면에 대한 2차원 배열의 열 인덱스는 위부터 아래로 0~2, 행은 좌부터 우로 0~2이다.

배열에서 가장 쉽고 빠르게 한 줄을 삭제 및 삽입을 할 수 있는 방법은 stack구조의 pop, append이다.

pop()으로 저 검정 줄을 없앨 수 있으면 모든 면에 대해서 동일한 logic으로 위 동작을 구현할 수 있다.

 

Front를 시계방향으로 돌리는 경우를 다시 보면

Up의 가장 아래에 있는 줄은 Right의 좌측 줄로 이동한다.

Up의 가장 아래 : Up.pop()로 간단히 뽑아올 수 있다 = 모든 검정 줄을 가장 아래로 보내자

 

 

 

기준 면 Front와 비교 면 (U, L, R, D) 에 대하여

U : 기준 면과 맞닿아 있는 비교 면의 변이 아래인 경우엔 0도 회전

L : 기준 면과 맞닿아 있는 비교 면의 변이 우측인 경우엔 90도 회전

R : 기준 면과 맞닿아 있는 비교 면의 변이 좌측인 경우엔 270도 회전

D : 기준 면과 맞닿아 있는 비교 면의 변이 윗쪽인 경우엔 180도 회전

 

회전변환 후 좌측 그림처럼 pop, append를 반복한다. 이후 회전시킨 면들을 다시 원상복구하면 인접한 4개의 면을 회전하는 동작의 구현이 완료가 된다.

 

 

 

위 과정을 구현하기 위해 약간의 노가다가 필요했다. 모든 면에 대해 맞닿아 있는 비교 면의 변의 방향을 보고 

아래 : 0

우측 : 90

좌측 : 270

위 : 180

으로 저장한다. 또한 저장할 때 순서는 기준면을 기준으로 시계방향으로 (F의 경우 URDL) 저장한다.

        self.rot_info = {
            "U":{"B":0,     "R":180,    "F":180,    "L":180,},
            "D":{"F":0,     "R":0,      "B":180,    "L":0,},
            "F":{"U":0,     "R":270,    "D":180,    "L":90,},
            "B":{"D":0,     "R":90,     "U":180,    "L":270,},
            "L":{"U":270,   "F":270,    "D":270,    "B":270,},
            "R":{"U":90,    "B":90,     "D":90,     "F":90,},
        }

이렇게 구해둔 rot_info를 활용하여 다음과 같이 시계방향 회전을 구현할 수 있다.

    def process(self, rot_seq):
        tmp = self.cubic[rot_seq[3]].pop()
        for i in range(3,0,-1):
            l, r = rot_seq[i], rot_seq[i-1]
            self.cubic[l].append(self.cubic[r].pop())
        self.cubic[rot_seq[0]].append(tmp)

    def rot90(self, surface):
        surface_rot_info = self.rot_info[surface]
        for s, d in surface_rot_info.items():
            self.lot_surface(s,d)

        self.process(list(surface_rot_info.keys()))
        self.lot_surface(surface)
        for s, d in surface_rot_info.items():
            self.lot_surface(s, 360-d)

이제 반시계만 구현하면 된다.

 

회전 방식의 단순화

반시계는 어떻게 표현이 가능할까?

시계방향을 90도 회전이라고 하면, 반시계방향은 270(90*3) 도 회전이다.

단순히 시계방향으로 90도 회전을 3번 하면 반시계 방향으로 회전한 것과 같은 결과가 나온다.

    def turn(self, surface, method):
        for _ in range(1 if method=="+" else 3):
            self.rot90(surface)

 

이제 문제 조건에 맞게 위에서 본 큐브의 색깔을 출력하는 코드를 짜고,

    def print(self, surface="U"):
        for l in self.cubic[surface]:
            print(*l, sep="")

 

입력을 받아 역할을 수행하는 메인 코드를 작성한다.

if __name__=="__main__":
    n = int(input())
    for tc in range(n):
        _ = input()
        cubic = Cubic()
        for cmd in input().split():
            cubic.turn(*list(cmd))
        cubic.print()

---

 

구현 문제는 언제나 고통스럽다. 출제 의도가 구현이라면 빠르게 눈치채고 최대한 단순하게 풀어내는게 코딩테스트를 통과하는데 꽤나 큰 도움이 되는 것 같다.

 

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