백준 온라인 저지 BOJ Question 5373 - 큐빙
마지막으로 코드리뷰를 하고 나서 4주가 조금 안 되는 시간이 흘렀다. 보통 2주 정도면 올리곤 했었는데, 그 사이 나름의 사건들이 있었기도 하고, 풀었던 문제들이 굳이 리뷰를 할 만큼 큰 감동이 있지도 않았다.
나는 현재 BOJ문제집의 베스트셀러인 삼성 SW 역량테스트 기출문제집을 풀고있다. 이전에 올렸던 2048 또한 삼성 SW 역량테스트 기출문제였고 오늘 리뷰하고자 하는 문제 또한 그렇다. 하지만 이 문제는 BOJ에서 제공하는 solved.ac의 난이도 평가가 기출문제 중 가장 높은 플래티넘 V이고 동시에 내가 풀어낸 문제 중 현재로서는 가장 고난도였기에 다시 한번 리뷰해본다.
- Given )
- 3*3*3 크기의 큐브가 주어지며, 이 문제에서의 큐브는 모두 맞춰진 상태로 주어진다. 위/아래/앞/뒤/왼쪽/오른쪽 순으로 흰색/노란색/빨간색/주황색/초록색/파란색 이 칠해져있다.
- Input )
- 첫째 줄에 테스트 케이스의 개수 n 이 주어진다. ( 1 <= n <= 1,000 )
- 둘째 줄에는 큐브를 돌리는 방법이 주어지며, 각 방법은 공백으로 구분된다.
첫 문제는 돌린 면 ( Up/Down/Front/Back/Left/Right ), 두 번째 문자는 돌린 방향이다. 각 면을 정면으로 바라보았을 때 + 는 시계방향, - 는 반시계 방향을 의미한다.
- Output )
- 각 테스트 케이스를 모두 돌린 후의 윗면의 색상을 출력하라. 뒷면과 접하는 모서리가 위로 가는 방향이 정방향이다.
Approach ) 회전면과 접해있는 방향에 따라 각 면의 색상 또한 달라진다. 각 면의 9칸을 모두 행렬화 하고, 해당 면이 움직이는 경우를 지정하자.
우선 문제에 대한 나의 첫 접근방법은 각 면을 모두 행렬화 하여 각 면이 회전할 때 영향을 받는 면을 헷갈리지 않도록 지정해 놓는 방향이었다. 문제를 풀기 시작할 때 시간 복잡도에 대해서까지 생각했었는지는 확실하지 않으나, 우선 문제에 한 테스트 케이스에 최대 회전 횟수가 적혀있지 않은 것을 미루어보아 시간을 빡빡하게 쪼아서 변별력을 내는 문제가 아닌 구현을 제대로 해내는가에 대한 문제라고 생각된다.
추가로 이 글을 검색해서 찾아 들어왔다면, 해당 문제를 풀고자 하는 사용자일 수 있으니 밑의 코드를 보기 전에, 먼저 소개해주는 사이트에서 큐브를 직접 굴려가며 자신의 코드 어느 부분에서 문제가 발생하는지 우선적으로 찾아보는 것을 추천한다.
https://rubiks-cube-solver.com/ko/
루빅 큐브 맞추기
온라인 루빅 큐브 맞추기는 뒤섞인 루빅 큐브를 푸는데 필요한 계산을 합니다. 귀하의 뒤섞인 퍼즐의 색깔을 입력하고 풀기 버튼을 눌러주세요. 그 다음 프로그램에 의해 제공된 지시를 따라 주
rubiks-cube-solver.com
def turn(d,x): # << direction & surface
tmp = [i[:] for i in x]
if d == '-':
for i in range(3):
x[2][i],x[1][i],x[0][i] = tmp[i][0],tmp[i][1],tmp[i][2]
else:
for i in range(3):
x[0][-(1+i)],x[1][-(1+i)],x[2][-(1+i)] = tmp[i][0],tmp[i][1],tmp[i][2]
return x큐브를 돌릴 때 정면을 감싸는 네 면의 한 줄이 회전하지만, 가장 먼저 정면 또한 회전한다. 따라서 정면의 3*3 매트릭스의 회전 함수를 작성했다. 행렬 회전 함수는 이보다 더 간단한 문제로 다루는 경우가 많으므로 굳이 설명을 덧붙이진 않겠다.
def move(d,x):
global U,D,F,B,L,R
dic[dic[x]] = turn(d,dic[dic[x]])
if x == 'U': #done
if d == '-':
L[0],B[0],R[0],F[0] = B[0],R[0],F[0],L[0]
else:
L[0],B[0],R[0],F[0] = F[0],L[0],B[0],R[0]
elif x == 'D':
if d == '+':
L[2],B[2],R[2],F[2] = B[2],R[2],F[2],L[2]
else:
L[2],B[2],R[2],F[2] = F[2],L[2],B[2],R[2]
elif x== 'F':
key = dic[x]
t,r,b,l = [dic[i] for i in comb[key]]
tmp1,tmp2 = t[2][:],b[0][:]
if d == '+':
t[2],b[0] = list(reversed([i[2] for i in l])),list(reversed([j[0] for j in r]))
for i in range(3):
r[i][0],l[i][2] = tmp1[i],tmp2[i]
else:
b[0],t[2] = [i[2] for i in l],[j[0] for j in r]
for i in range(3):
r[i][0],l[i][2] =tmp2[-(1+i)], tmp1[-(1+i)]
elif x == 'B':
key = dic[x]
t,r,b,l = [dic[i] for i in comb[key]]
tmp1,tmp2 = list(reversed(t[0][:])),b[2][:]
if d == '+':
t[0],b[2] = [i[2] for i in l],[j[0] for j in r]
for i in range(3):
r[i][0],l[i][2] = tmp1[i],tmp2[-(1+i)]
else:
b[2],t[0] = list(reversed([i[2] for i in l])),list(reversed([j[0] for j in r]))
for i in range(3):
r[i][0],l[i][2] =tmp2[i], tmp1[-(1+i)]
elif x == 'L':
key = dic[x]
t,r,b,l = [dic[i] for i in comb[key]]
if d == '+':
for i in range(3):
t[i][0],b[i][0],r[i][0],l[-(1+i)][2] = l[-(1+i)][2],r[i][0],t[i][0],b[i][0]
else:
for i in range(3):
t[i][0],l[-(1+i)][2],b[i][0],r[i][0] = r[i][0],t[i][0],l[-(1+i)][2],b[i][0]
elif x== 'R':
key = dic[x]
t,r,b,l = [dic[i] for i in comb[key]]
if d == '+':
for i in range(3):
t[i][2],r[-(1+i)][0],b[i][2],l[i][2] = l[i][2],t[i][2],r[-(1+i)][0],b[i][2]
else:
for i in range(3):
t[i][2],r[-(1+i)][0],b[i][2],l[i][2] = r[-(1+i)][0],b[i][2],l[i][2],t[i][2]
n = int(input())
for i in range(n):
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)]
dic = {0:U,1:D,2:F,3:B,4:L,5:R,'U':0,'D':1,'F':2,'B':3,'L':4,'R':5}
comb = [[3,5,2,4],[2,5,3,4],[0,5,1,4],[0,4,1,5],[0,2,1,3],[0,3,1,2]]
m = int(input())
lst = input().split()
for j in lst:
x,d = list(j)
move(d,x)
for q in U:
a = ''
for w in q: # 문제의 출력방식을 따라가기 위함
a += w
print(a)나의 큐빙 구현 요소는 다음과 같았다.
- 각 면의 회전에 영향을 받는 면을 리스트에 따로 관리
- 1의 리스트 호출을 위해 각 문자를 숫자로 바꿀 딕셔너리 생성
- move 함수 작성을 통해 각 면마다 특수한 움직임 구현
많은 면을 회전시키는 코드를 작성해야 하기 때문에 내가 헷갈리지 않도록 각 면의 회전에 따른 영향을 받는 면을 가장 우선적으로 정리하고 시작할 필요가 있었다.
(1) U/D/F/B/L/R 순으로 0~5의 가상의 인덱스를 부여하고 윗면부터 시작하여 윗면의 위/오른쪽/아래/왼쪽 면인 [뒷면/오른쪽면/앞면/왼쪽면]을 comb라는 리스트 중 U의 인덱스에 해당하는 0번째 리스트에 삽입했다. 해당 방식을 따라 모든 면의 회전 시 영향을 받는 면을 모두 정리하여 comb 리스트에 관리해두었다. 앞서 리스트에 가상의 인덱스를 부여했지만,
(2) 매 move 함수 호출시마다 바로 해당 리스트를 불러올 수 있게 해당 면의 회전이 호출될 때마다 문자를 해당 리스트 인덱스로 바꿔 줄 딕셔너리를 생성해주었다.
(3) 앞서서 구현한 turn 함수를 move 함수 내에서 우선적으로 실행시켰다. 회전하는 면의 정면은 나머지 면과 전혀 연관이 없으므로 그저 회전만 시켜주면 끝이다.
문제를 풀기 시작할 땐 위와 같은 요소를 가지고 한 행 혹은 한 열을 슬라이스 해 와서 움직임에 따라 그대로 갖다 넣으면 구현이 될 것이라 생각했다. 하지만, 처음 생각과는 다르게 Front 면을 구현할 때부터 바로 문제가 발생했다. Up 면이 Left 면으로 이동할 때 그대로 이동하여 순서가 역순이 되어버렸다. 해당 문제를 reversed 함수를 통해 해결하긴 했으나, 지금 다시 들여다보니 reversed 함수 대신 for 문 내의 입력을 받는 부분에서의 i를 -(i+1) 정도로 바꿔도 가능했을 듯하다.
[[ 마무리 ]]
내가 짜 놓은 코드라서 그런지, 그다지 참신한 방법으로 구현하진 못했다고 생각이 든다. 하지만 굳이 높은 점수를 주자면 내가 코딩을 하는데 앞서서 각 면의 회전에서 영향받는 면을 헷갈리지 않도록 리스트로 관리한 점이 작성하고 나니 참 괜찮은 방향이었던 것 같다. 특히 구현 문제에서는 예제로 주어지는 간단한 문제를 구현시키느라 러프한 코드를 짜다보면 결국 본 문제에서 함정에 빠지곤 한다. 그렇다고 디테일하게 구현하려 하다 보면 그걸 계속해서 되뇌다 자가당착에 빠진다. 나름 나 혼자 헷갈리는 부분을 최소화하며 풀고자 했던 문제였다. ( 추가로 왜 그렇게 높은 등급의 문제인지는 잘 이해가 안 된다. )
최근댓글