백준 5373 : 큐빙(파이썬)

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

5373번: 큐빙

문제자체는 간단하지만, 정말 구현하기가 힘든 문제.

대부분 많이 틀린 것 같은데, 이유는 정말 알기 힘든 것 같다.

나의 경우는 인덱싱 문제. 하드코딩을 하고 틀렸다는 결과를 보게 된다면, 인덱스 참조부터 잘 확인해야할 것 같다.

 

돌리고 돌리다보니 헷갈려서 인덱스 지정을 잘못주었다는 것을 뒤늦게 확인했다.

또한, 경우의 수가 너무 많아 반례를 찾기가 정말 어렵다. (웬만하면 대부분의 케이스에 대해서 맞기 때문에 환장할 노릇)

코드를 자세히 뜯어보니 결국에 해당 문제는 인덱싱에서 오류가 난 것을 발견할 수 있었고, 차근차근 다시 수정해보니 정답처리를 받을 수 있었다.

 

 1. 큐브 리스트 만들기

 큐브 리스트는 전부 1차원으로 만들어주었다. 하나의 면 입장으로 생각해보면 톱니바퀴 문제처럼 돌아가는 꼴이기 때문에 굳이 2차원 배열이 필요없다. 가운데는 고정이기 때문에 바깥쪽으로 좌상단을 0으로 만들고 시계방향으로 리스트를 구성했다.

 

 2. 큐브면 정의

 이 문제의 핵심은 큐브를 회전시킬 때 적절하게 인덱싱해서 회전시키려는 면과 해당 면과 접해있는 인접 면들의 정보를 바꿔주는 것이다. 큐브를 펼쳐보면 다음과 같다.

큐브
			0	1	2
			7	o	3
			6	5	4
0	1	2	0	1	2	0	1	2	0	1	2
7	g	3	7	w	3	7	b	3	7	y	3
6	5	4	6	5	4	6	5	4	6	5	4
			0	1	2
			7	r	3
			6	5	4

윗면(U)를 기준으로 왼쪽 위부터 인덱스를 부여했을 때 다음과 같이 정의할 수 있다. 해당 좌표를 토대로 윗면(U), 아랫면(D), 앞면(F), 뒷면(B), 왼쪽면(L), 오른쪽(R)면을 정의하면 다음과 같이 표현할 수 있다.

< 보는 방향에 따른 각 면들의 인덱스 정보 >

각 면마다 다음과 같이 정리할 수 있다. 이제 관심영역은 아래의 그림과 같으므로, 인접면들에 대한 정보는 1차원 리스트로 받아서 조건에 따라 돌려주고, 바라보는 면도 돌려주면 된다. 1차원 리스트 순서는 중심면에서 위에서 시계방향 순으로 결정했다. 

<윗면의 경우에 참조할 인덱스>

왼쪽면과 오른쪽면의 경우에는 바라보는 중심면의 인덱스 정보가 위치와 다르게 배치되어있다. 항상 배열의 인덱스는 좌상단부터 시작하므로, 틀어진 만큼 돌려준 상태에서 회전을 시키고, 회전이 끝난후 다시 원상태로 만들어주면 된다. 예를 들어 왼쪽면의 경우에는 초록면의 (0, 0) 값이 (0, 2)에 해당하는 값이 옮겨져 있으므로, 큐브 회전하기 전에 미리 돌려주는 식이다. 이거 설정해주다가 인덱스 정보 헷갈려서 고생을 많이 했다.

 

 3. 전체 코드

메모리 : 130808 KB 시간 : 276 ms

하드코딩은 이제 할 줄 알겠으니까 다음에 풀어볼땐 좀 더 컴팩트하게 만들어봐야겠다.

몰랐는데 플5 문제라고 하네.. 알았으면 빠르게 포기할 뻔했다.

n = int(input())
# 큐브 돌린 횟수
info_t = []
for i in range(n):
    t = int(input())
    info = list(map(str, input().split()))
    info_t.append(info)


def turn(main_x, x1, x2, x3, x4, d, f):
    if f == 'U':
        ex_turn = [x1[6], x1[5], x1[4], x2[0], x2[7], x2[6], x3[2], x3[1], x3[0], x4[4], x4[3], x4[2]]
    elif f == 'D':
        ex_turn = [x1[6], x1[5], x1[4], x2[4], x2[3], x2[2], x3[2], x3[1], x3[0], x4[0], x4[7], x4[6]]
    elif f == 'F':
        ex_turn = [x1[6], x1[5], x1[4], x2[6], x2[5], x2[4], x3[2], x3[1], x3[0], x4[6], x4[5], x4[4]]
    elif f == 'B':
        ex_turn = [x1[6], x1[5], x1[4], x2[2], x2[1], x2[0], x3[2], x3[1], x3[0], x4[2], x4[1], x4[0]]
    elif f == 'L':
        ex_turn = [x1[0], x1[7], x1[6], x2[0], x2[7], x2[6], x3[0], x3[7], x3[6], x4[0], x4[7], x4[6]]
        for i in range(2):
            main_x.insert(0, main_x[-1])
            del main_x[-1]
    elif f == 'R':
        ex_turn = [x1[4], x1[3], x1[2], x2[4], x2[3], x2[2], x3[4], x3[3], x3[2], x4[4], x4[3], x4[2]]
        for i in range(2):
            main_x.append(main_x[0])
            del main_x[0]
    if d == '+':  # 시계 방향으로 돌기
        for i in range(3):
            ex_turn.insert(0, ex_turn[-1])
            del ex_turn[-1]
            if i < 2 :
                main_x.insert(0, main_x[-1])
                del main_x[-1]
    else:  # 반 시계 방향으로 돌기
        for i in range(3):
            ex_turn.append(ex_turn[0])
            del ex_turn[0]
            if i < 2 :
                main_x.append(main_x[0])
                del main_x[0]
    if f == 'U':
        x1[6], x1[5], x1[4] = ex_turn[0], ex_turn[1], ex_turn[2]
        x2[0], x2[7], x2[6] = ex_turn[3], ex_turn[4], ex_turn[5]
        x3[2], x3[1], x3[0] = ex_turn[6], ex_turn[7], ex_turn[8]
        x4[4], x4[3], x4[2] = ex_turn[9], ex_turn[10], ex_turn[11]
    elif f == 'D':
        x1[6], x1[5], x1[4] = ex_turn[0], ex_turn[1], ex_turn[2]
        x2[4], x2[3], x2[2] = ex_turn[3], ex_turn[4], ex_turn[5]
        x3[2], x3[1], x3[0] = ex_turn[6], ex_turn[7], ex_turn[8]
        x4[0], x4[7], x4[6] = ex_turn[9], ex_turn[10], ex_turn[11]
    elif f == 'F':
        x1[6], x1[5], x1[4] = ex_turn[0], ex_turn[1], ex_turn[2]
        x2[6], x2[5], x2[4] = ex_turn[3], ex_turn[4], ex_turn[5]
        x3[2], x3[1], x3[0] = ex_turn[6], ex_turn[7], ex_turn[8]
        x4[6], x4[5], x4[4] = ex_turn[9], ex_turn[10], ex_turn[11]
    elif f == 'B':
        x1[6], x1[5], x1[4] = ex_turn[0], ex_turn[1], ex_turn[2]
        x2[2], x2[1], x2[0] = ex_turn[3], ex_turn[4], ex_turn[5]
        x3[2], x3[1], x3[0] = ex_turn[6], ex_turn[7], ex_turn[8]
        x4[2], x4[1], x4[0] = ex_turn[9], ex_turn[10], ex_turn[11]
    elif f == 'L':
        x1[0], x1[7], x1[6] = ex_turn[0], ex_turn[1], ex_turn[2]
        x2[0], x2[7], x2[6] = ex_turn[3], ex_turn[4], ex_turn[5]
        x3[0], x3[7], x3[6] = ex_turn[6], ex_turn[7], ex_turn[8]
        x4[0], x4[7], x4[6] = ex_turn[9], ex_turn[10], ex_turn[11]
        for i in range(2):
            main_x.append(main_x[0])
            del main_x[0]
    elif f == 'R':
        x1[4], x1[3], x1[2] = ex_turn[0], ex_turn[1], ex_turn[2]
        x2[4], x2[3], x2[2] = ex_turn[3], ex_turn[4], ex_turn[5]
        x3[4], x3[3], x3[2] = ex_turn[6], ex_turn[7], ex_turn[8]
        x4[4], x4[3], x4[2] = ex_turn[9], ex_turn[10], ex_turn[11]
        for i in range(2):
            main_x.insert(0, main_x[-1])
            del main_x[-1]
    return main_x, x1, x2, x3, x4


def solve():
    it = 0
    while it < n:
        cw, cy, cr, co, cg, cb = ['w'] * 8, ['y'] * 8, ['r'] * 8, ['o'] * 8, ['g'] * 8, ['b'] * 8
        for tt in range(len(info_t[it])):
            face = info_t[it][tt][0]
            direction = info_t[it][tt][1]
            if face == 'U':
                cw, co, cb, cr, cg = turn(cw, co, cb, cr, cg, direction, face)
            elif face == 'D':
                cy, cr, cb, co, cg = turn(cy, cr, cb, co, cg, direction, face)
            elif face == 'F':
                cr, cw, cb, cy, cg = turn(cr, cw, cb, cy, cg, direction, face)
            elif face == 'B':
                co, cy, cb, cw, cg = turn(co, cy, cb, cw, cg, direction, face)
            elif face == 'L':
                cg, cw, cr, cy, co = turn(cg, cw, cr, cy, co, direction, face)
            elif face == 'R':
                cb, cw, co, cy, cr = turn(cb, cw, co, cy, cr, direction, face)
        upper = [[cw[0], cw[1], cw[2]], [cw[7], 'w', cw[3]], [cw[6], cw[5], cw[4]]]
        for i in range(len(upper)):
            print(*upper[i], sep="")
        it += 1
    return

solve()