블로그에 코테 문제는 업로드해야지

제일 풀기 귀찮았던 문제를 풀었습니다. 최근에 딥러닝에서 행렬 연산이 그림이 잘 안그려지길래 머리에 윤활유를 뿌릴 겸 기하(?)-구현을 선택해봤습니다.

구현 고민

문제는 상당히 쉽습니다. 큐브를 돌려서 상태를 나타내는 문제입니다. 하지만 딱 봐도 구현이 매우 번거롭고, 저는 3~4시간쯤 쓴거같네요 :(

저는 문제를 정의하는 시간이 가장 오래걸렸습니다. 좀 여러가지 방법으로 구현 방법을 생각해봤습니다.

1. 회전 당 바뀌는 면을 하드 구현

이 방식으로 하면 전개도 상 넘버링이 상당히 귀찮습니다. 이 방식으로 구현했으면 꽤 빠르게 끝낼 수 있었겠지만, 저는 좀 포괄적인 풀이를 원했습니다.

2. 모든 면을 구현하지 말고, 각 변을 돌릴 때마다 그 변이 U이 되도록 상태를 변화시키고 복원하기 반복

흔히 삼성 코테에서 2차원 배열 회전에서 사용하는 테크닉으로 특정 행위를 한 변에서만 정의하는 것입니다. 만약 한 회전만 정의할 수 있다면 상태 변환 코드만 짜면 6방향에 대해 다 똑같이 정의할 수 있지만, 이것도 까다로웠습니다.

3. 큐브의 각 작은 정육면체 단위(큐빅)로 살피기

저는 그래서 이 큐브를 어떻게 하면 포괄적으로 정의할 수 있을까를 고민해보았습니다. 그렇게 작은 정육면체 단위로 살펴보았습니다.

각 큐빅는 1~3면이 색이 있고 나머지는 내부에 있고 UDFBLR의 특성을 거의 같게 지니고 있습니다. 그럼 이제 우리가 고민해야할 함수는 2가지 입니다.

  1. 333내에서 위치의 변화
  2. 큐브에 따른 xyz 축 기준 회전

그런데 333으로 넘버링을 하면 한변의 큐빅은 규칙적인 방법으로 넘버링이 됩니다. (양옆으로 등차, 위아래로 등차) 쉽게 호출할 수 있고, 시계방향 회전은 반복문으로 쉽게 구현할 수 있습니다.

그리고 큐브에 따른 xyz 축 기준 회전은 시계방향 총 3가지 상태만 정의하면 나머지 반시계방향은 시계방향*3으로 정의할 수 있습니다. 회전도 다음 상태를 알면 반복문으로 쉽게 구현할 수 있습니다.

결국 i나 ii 연산은 바꿀 index만 정의하면 전체적인 과정은 재배치라 구현이 좀 편할 것 같았고, 이제 이 아이디어로 구현했습니다.

구현 코드

# [BOJ 5573] 큐빙 : https://www.acmicpc.net/problem/5373
# tag : 구현, 기하
# solution by @subinium

# ufl : 큐브별로 UFL 회전시 각면이 바라보는 방향 변화
# cw : 시계방향으로 돌리는 경우 3 * 3에서 변화되는 내용
ufl, cw = ['015423', '452310', '320145'], '258147036'

# 3 * 3 * 3에서 한 변을 뽑는 방법
# 한 변의 숫자는 반드시 순서대로 등차수열임을 활용
def side_(ith, st, a, b):
    return [st+a*(i % 3)+b*(i//3)-1 for i in range(9)]

# UDFBLR 순서에서 각 변을 얻기 위한 상수값 사용
side = [side_(i, *stab) for i, stab in enumerate([(1, 1, 3),
                                                  (19, 3, 1), (7, 1, 9), (1, 9, 1), (1, 3, 9), (3, 9, 3)])]

# 기존의 배치에서 바뀐 부분만 재배치
# a, st, ed : 배열, 기존위치, 바뀐위치
def realign(a, st, ed):
    ret = a[:]
    for s, e in zip(st, ed):
        ret[int(e)] = a[int(s)]
    return ret

# 한 변을 돌리는 함수 / 큐브의 위치와 상태 변경
# 시계방향 또는 반시계방향 중 하나만 정의 => 반시계 == 시계*3
def rotate(op, pos, state):
    idx, ccw = 'UDFBLR'.index(op[0]), op[1]  # 변확인 및 시계/반시계 방향 확인
    blocks = side[idx]  # 볼 변의 번호들만 선택
    # 큐브의 위치 변경
    for i in range(1+(ccw == '+')*2):
        blocks = realign(blocks, range(9), cw)
    pos = realign(pos, side[idx], blocks)

    # 큐브의 상태 변경
    for i in range(1+((ccw == '+') ^ (idx % 2))*2):
        for j in range(9):  # 한변당 큐브의 개수 9개
            state[pos[blocks[j]]] = realign(
                state[pos[blocks[j]]], range(6), ufl[idx//2])

    return pos, state

# 초기 상태 pos, state 정의
# pos[i] : 매 상태에서 3 * 3 * 3에서 순서대로 넘버링했을 때, i번쨰 큐브의 번호
# state[i] : 초기 i번 큐브의 상태
def init():
    pos, state = [i for i in range(27)], [
        [0 for _ in range(6)] for i in range(27)]
    for idx, col in enumerate('wyrogb'):
        for block in side[idx]:
            state[block][idx] = col
    return pos, state

# 각 과정별 함수
def process():
    N = input()
    # 회전 별로 pos, state 변경
    pos, state = init()  # 초기화
    for order in input().split():
        pos, state = rotate(order, pos, state)

    # 윗면 큐브들에서 위만 출력
    for i, idx in enumerate(side[0]):
        print(state[pos[idx]][0], end=''+(i % 3 == 2)*'\n')


# Main 함수
if __name__ == '__main__':
    # 테스트 케이스 별 과정 진행
    TC = int(input())
    for _ in range(TC):
        process()

Leave a Comment