블로그에 코테 문제는 업로드해야지
제일 풀기 귀찮았던 문제를 풀었습니다. 최근에 딥러닝에서 행렬 연산이 그림이 잘 안그려지길래 머리에 윤활유를 뿌릴 겸 기하(?)-구현을 선택해봤습니다.
구현 고민
문제는 상당히 쉽습니다. 큐브를 돌려서 상태를 나타내는 문제입니다. 하지만 딱 봐도 구현이 매우 번거롭고, 저는 3~4시간쯤 쓴거같네요 :(
저는 문제를 정의하는 시간이 가장 오래걸렸습니다. 좀 여러가지 방법으로 구현 방법을 생각해봤습니다.
1. 회전 당 바뀌는 면을 하드 구현
이 방식으로 하면 전개도 상 넘버링이 상당히 귀찮습니다. 이 방식으로 구현했으면 꽤 빠르게 끝낼 수 있었겠지만, 저는 좀 포괄적인 풀이를 원했습니다.
2. 모든 면을 구현하지 말고, 각 변을 돌릴 때마다 그 변이 U이 되도록 상태를 변화시키고 복원하기 반복
흔히 삼성 코테에서 2차원 배열 회전에서 사용하는 테크닉으로 특정 행위를 한 변에서만 정의하는 것입니다. 만약 한 회전만 정의할 수 있다면 상태 변환 코드만 짜면 6방향에 대해 다 똑같이 정의할 수 있지만, 이것도 까다로웠습니다.
3. 큐브의 각 작은 정육면체 단위(큐빅)로 살피기
저는 그래서 이 큐브를 어떻게 하면 포괄적으로 정의할 수 있을까를 고민해보았습니다. 그렇게 작은 정육면체 단위로 살펴보았습니다.
각 큐빅는 1~3면이 색이 있고 나머지는 내부에 있고 UDFBLR의 특성을 거의 같게 지니고 있습니다. 그럼 이제 우리가 고민해야할 함수는 2가지 입니다.
- 333내에서 위치의 변화
- 큐브에 따른 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