백준 5373 큐빙 -(Python)

문제

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

나의 접근법

첫번째 

저는 처음에 윗면을 기준으로 규칙성을 찾으려고 했습니다. 하지만 시간이 너무 오래걸리고 다른 면에서의 규칙성과 윗면에서의 규칙성을 못찾아서 위 방법은 포기했습니다. 그리고 결국 제가 정한 시간이 초과되어 구글링을 통해 다른 사람들은 어떻게 규칙을 찾았는지 검색해보았습니다. 하지만 대부분의 답에서 일일이 각 면에 해당하는 코드를 작성한 것을 보고 저도 규칙성 보다는 일일이 구현하기로 결정했습니다. 이 방법이 귀찮기는 하지만 때로는 가장 확실한 방법인 것 같습니다.

 

두번째

 

세번째 풀이

두번째 풀이에서 전개로를 활용했습니다. 각 회전하는 면을 기준으로 상하좌우 3칸만 회전하는 변화만 파악하여 빠르게 파악하여 if문으로 각 경우의 수 만큼 대입을 시켜주었더니 풀 수 있었습니다. 

세번째 풀이를 푸는데 큰 도움을 얻은 사이트가 있습니다. 위 문제는 인덱스가 너무 많아서 자칫 실수하기 쉬운데

https://rubiks-cube-solver.com/fr/ 에서 전개도를 펼쳐 큐브를 직접 돌려가며 푸니 에러도 쉽게 찾고 디버그도 정말 빠르게 했습니다.

처음 이 문제를 풀다가 구글링을 할 때 굳이 이렇게 까지 찾아가며 풀어야 하나 하는 생각도 들었는데 위 문제를 접하고 진짜 풀고 싶다고 마음먹으니 위 사이트가 정말 많이 도움이 되었습니다. 저도 각 D면의 대입에서 에러를 금방 찾을 수 있었습니다. 

정답 코드

import sys

def rotate(side, clockWise):
    if clockWise == '+':
        temp = [side[0][0], side[0][1], side[0][2]]
        side[0][0], side[0][1], side[0][2] = side[2][0], side[1][0], side[0][0]
        side[0][0], side[1][0], side[2][0] = side[2][0], side[2][1], side[2][2]
        side[2][0], side[2][1], side[2][2] = side[2][2], side[1][2], side[0][2]
        side[2][2], side[1][2], side[0][2] = temp[2], temp[1], temp[0]
    else:
        temp = [side[0][0], side[0][1], side[0][2]]
        side[0][0], side[0][1], side[0][2] = side[0][2], side[1][2], side[2][2]
        side[0][2], side[1][2], side[2][2] = side[2][2], side[2][1], side[2][0]
        side[2][2], side[2][1], side[2][0] = side[2][0], side[1][0], side[0][0]
        side[2][0], side[1][0], side[0][0] = temp[0], temp[1], temp[2]
    return side

def sol(d, clockWise):
    global U, F, R, L, D, B
    if d == 'U':
        if clockWise == '+':
            U = rotate(U, '+')
            temp = [F[0][0], F[0][1], F[0][2]]
            F[0][0], F[0][1], F[0][2] = R[0][0], R[0][1], R[0][2]
            R[0][0], R[0][1], R[0][2] = B[0][0], B[0][1], B[0][2]
            B[0][0], B[0][1], B[0][2] = L[0][0], L[0][1], L[0][2]
            L[0][0], L[0][1], L[0][2] = temp[0], temp[1], temp[2]
        else:
            U = rotate(U, '-')
            temp = [F[0][0], F[0][1], F[0][2]]
            F[0][0], F[0][1], F[0][2] = L[0][0], L[0][1], L[0][2]
            L[0][0], L[0][1], L[0][2] = B[0][0], B[0][1], B[0][2]
            B[0][0], B[0][1], B[0][2] = R[0][0], R[0][1], R[0][2]
            R[0][0], R[0][1], R[0][2] = temp[0], temp[1], temp[2]
    elif d == 'F':
        if clockWise == '+':
            F = rotate(F, '+')
            temp = [U[2][0], U[2][1], U[2][2]]
            U[2][0], U[2][1], U[2][2] = L[2][2], L[1][2], L[0][2]
            L[2][2], L[1][2], L[0][2] = D[0][2], D[0][1], D[0][0]
            D[0][2], D[0][1], D[0][0] = R[0][0], R[1][0], R[2][0]
            R[0][0], R[1][0], R[2][0] = temp[0], temp[1], temp[2]
        else:
            F = rotate(F, '-')
            temp = [U[2][0], U[2][1], U[2][2]]
            U[2][0], U[2][1], U[2][2] = R[0][0], R[1][0], R[2][0]
            R[0][0], R[1][0], R[2][0] = D[0][2], D[0][1], D[0][0]
            D[0][2], D[0][1], D[0][0] = L[2][2], L[1][2], L[0][2]
            L[2][2], L[1][2], L[0][2] = temp[0], temp[1], temp[2]
    elif d == 'R':
        if clockWise == '+':
            R = rotate(R, '+')
            temp = [U[0][2], U[1][2], U[2][2]]
            U[0][2], U[1][2], U[2][2] = F[0][2], F[1][2], F[2][2]
            F[0][2], F[1][2], F[2][2] = D[0][2], D[1][2], D[2][2]
            D[0][2], D[1][2], D[2][2] = B[2][0], B[1][0], B[0][0]
            B[2][0], B[1][0], B[0][0] = temp[0], temp[1], temp[2]
        else:
            R = rotate(R, '-')
            temp = [U[0][2], U[1][2], U[2][2]]
            U[0][2], U[1][2], U[2][2] = B[2][0], B[1][0], B[0][0]
            B[2][0], B[1][0], B[0][0] = D[0][2], D[1][2], D[2][2]
            D[0][2], D[1][2], D[2][2] = F[0][2], F[1][2], F[2][2]
            F[0][2], F[1][2], F[2][2] = temp[0], temp[1], temp[2]
    elif d == 'L':
        if clockWise == '+':
            L = rotate(L, '+')
            temp = [U[0][0], U[1][0], U[2][0]]
            U[0][0], U[1][0], U[2][0] = B[2][2], B[1][2], B[0][2]
            B[2][2], B[1][2], B[0][2] = D[0][0], D[1][0], D[2][0]
            D[0][0], D[1][0], D[2][0] = F[0][0], F[1][0], F[2][0]
            F[0][0], F[1][0], F[2][0] = temp[0], temp[1], temp[2]
        else:
            L = rotate(L, '-')
            temp = [U[0][0], U[1][0], U[2][0]]
            U[0][0], U[1][0], U[2][0] = F[0][0], F[1][0], F[2][0]
            F[0][0], F[1][0], F[2][0] = D[0][0], D[1][0], D[2][0]
            D[0][0], D[1][0], D[2][0] = B[2][2], B[1][2], B[0][2]
            B[2][2], B[1][2], B[0][2] = temp[0], temp[1], temp[2]

    elif d == 'B':
        if clockWise == '+':
            B = rotate(B, '+')
            temp = [U[0][0], U[0][1], U[0][2]]
            U[0][0], U[0][1], U[0][2] = R[0][2], R[1][2], R[2][2]
            R[0][2], R[1][2], R[2][2] = D[2][2], D[2][1], D[2][0]
            D[2][2], D[2][1], D[2][0] = L[2][0], L[1][0], L[0][0]
            L[2][0], L[1][0], L[0][0] = temp[0], temp[1], temp[2]
        else:
            B = rotate(B, '-')
            temp = [U[0][0], U[0][1], U[0][2]]
            U[0][0], U[0][1], U[0][2] = L[2][0], L[1][0], L[0][0]
            L[2][0], L[1][0], L[0][0] = D[2][2], D[2][1], D[2][0]
            D[2][2], D[2][1], D[2][0] = R[0][2], R[1][2], R[2][2]
            R[0][2], R[1][2], R[2][2] = temp[0], temp[1], temp[2]

    elif d == 'D':
        if clockWise == '+':
            D = rotate(D, '+')
            temp = [F[2][0], F[2][1], F[2][2]]
            F[2][0], F[2][1], F[2][2] = L[2][0], L[2][1], L[2][2]
            L[2][0], L[2][1], L[2][2] = B[2][0], B[2][1], B[2][2]
            B[2][0], B[2][1], B[2][2] = R[2][0], R[2][1], R[2][2]
            R[2][0], R[2][1], R[2][2] = temp[0], temp[1], temp[2]
        else:
            D = rotate(D, '-')
            temp = [F[2][0], F[2][1], F[2][2]]
            F[2][0], F[2][1], F[2][2] = R[2][0], R[2][1], R[2][2]
            R[2][0], R[2][1], R[2][2] = B[2][0], B[2][1], B[2][2]
            B[2][0], B[2][1], B[2][2] = L[2][0], L[2][1], L[2][2]
            L[2][0], L[2][1], L[2][2] = temp[0], temp[1], temp[2]

T = int(sys.stdin.readline().rstrip())
for i in range(T):
    U = [["w","w","w"], ["w","w","w"], ["w","w","w"]]
    F = [["r","r","r"], ["r","r","r"], ["r","r","r"]]
    R = [["b","b","b"], ["b","b","b"], ["b","b","b"]]
    L = [["g","g","g"], ["g","g","g"], ["g","g","g"]]
    B = [["o","o","o"], ["o","o","o"], ["o","o","o"]]
    D = [["y","y","y"], ["y","y","y"], ["y","y","y"]]

    n = int(input())
    data = list(input().split())
    for j in data:
        d, clockWise = j[0], j[1]
        sol(d, clockWise)
    for j in range(3):
        print(''.join(U[j]))

위 코드에서 중복성을 최대한 줄이기 위해 자기 면의 회전은 rotate라는 함수를 만들어 한번에 해결했습니다. 

 

테스트 케이스 뿐만 아니라 아래 반례까지 확인하시면 보다 정확한 답을 얻으실 수 있을것입니다. 

 

6
10
L+ U+ U- B+ F+ U- U+ L+ L- D+
10
B- U- L- L+ L- B+ L- R- U- F+
11
D+ F- D+ B+ R- L+ L+ U+ U+ B+ U-
11
D- U+ U+ R+ D- U+ B+ U- D+ F+ D-
11
D+ L- B- D- B- D+ U- B- L+ D- L-
11
B+ L- B+ R- F- U+ B+ U- B+ U+ U+

정답
bbb
oww
ggg
goo
www
yyr
ryy
rwb
wrr
gwo
gwr
bgb
wow
yww
rrg
bbo
owb
ggo

 

입력
6
5
U- R- U- D+ R-
6
L+ L+ F+ B+ U- L+
7
L- U- U+ U+ L+ R+ F-
7
D+ L- B- U+ D+ B+ B+
8
U- D+ B+ U+ D+ R- B- R+
9
B- L+ U- B+ B+ U+ D+ L+ B-

정답
oor
wwy
wwr
rwg
owg
yyg
wrb
wwr
bbb
yyb
wwg
wwg
bwr
wwb
wwr
bbw
owb
bwr

 

후기

삼성 SW 역량 기출문제만 집중적으로 풀고 있는중입니다. 난이도나 정답률은 고려하지 않고 위에서부터 차례로 풀고 있는 중입니다. 위 문제는 처음에 보자마자 포기하고 싶은 생각이 굴뚝 같았습니다. 3차원 도형의 큐브, 회전, 거기에 풀고싶지 않게 생긴 데이터 값들까지 쉬워보이는게 하나 없었습니다.

하지만 스스로 완벽하게 풀이는 못하더라도 문제를 이해하지도 않고 도전도 안해고보고 포기하는 제 자신이 싫었습니다.  계속 작은 어려움이 닥칠때마다 회피할 것 같았습니다. 그래서 문제부터 이해하려고 노력했습니다.

다행히 문제는 처음부터 잘 읽히고 데이터가 무슨 의미를 하며 결과가 왜 저렇게 나오는 지 쉽게 이해할 수 있었습니다. 이제 회전 전 전후를 비교하여 규칙을 찾고 이를 모듈화하여 문제를 해결하기만 하면 되었습니다. 하지만 너무 어려워 바로 구글을 통해 아이디어만 얻기로 했고 대부분의 블로거들도 많이 어려워하고 빡구현을 한 것을 보고 저도 따라서 빡구현을 해보았습니다.

맞추고 보니 플레 문제여서 놀랐지만 그만큼 어려웠던 것 같습니다.