정육면체 굴리기 (주사위 굴리기)

문제 출처 : 코드트리_정육면체 굴리기
티어 : 골드4
유형 : 시뮬레이션, BFS

출제 : 2016년 하반기 통합 1번
주의사항 : 주사위 구현방법을 확실히 정하고 들어갈 것!

---

주사위를 어떻게 구현할지에 따라 난이도가 달라지는 문제입니다. 저는 다행히 아이디어로 풀어냈지만, 생각이 나지 않는다면 노가다로라도 주사위의 움직임을 구현해야합니다. 하드코딩이 보통 속도와 메모리가 더 적게 들 뿐더러, 풀기만 하면 되는게 삼성 코딩테스트 아니겠어요?

---

생각의 흐름

저는 이 문제를 보고, 주사위를 위/아래 방향으로 굴리면 양 옆면이 변하지 않고, 양 옆으로 굴리면 위/아래면이 변하지 않는다는 사실을 이용해 전개도를 이용하기로 했습니다. 그래서 row, column이라는 두가지의 큐를 이용해 주사위의 움직임을 구현하자고 계획했고, 아랫면의 숫자와 이동방향은 그 큐의 인덱스를 이용하자고 생각했습니다. 그러면 아랫면의 숫자의 인덱스도 고정이 되 비교하기 쉬울거라 생각하고 문제를 풀었습니다.

스킬

이 문제의 스킬은 주사위를 두개의 큐로 표현하는 것입니다. 정육면체를 좌우로 굴린다고 했을 때, 절대로 위치가 바뀌지 않는 면이 두 개 있죠?

 

마찬가지로 상하로 굴러갈 때도 절대 움직이지 않는 면이 두 개 있습니다. 저는 여기에서 아이디어를 얻었는데요, 이 성질을 이용하면 주사위를 2차원 그래프가 아닌, 1차원 리스트형태 두 개로 관리할 수 있다는 것입니다. 한번 전개도로 살펴볼까요?

 

 

이렇게 윗면부터 맨 왼쪽 바닥으로 펼쳐본다면 주사위 아래와 같은 전개도가 나오는 것을 알 수 있습니다. 이를 오른쪽으로 회전했을 때, 위아래의 면은 그대로이며 좌우로 이어진 4개의 숫자는 왼쪽으로 한칸씩 이동했음을 알 수 있습니다. 이는 파이썬의 deque에 있는 rotate라는 함수로 구현할 수 있는데요, 그림으로 설명하면 아래와 같습니다.

 

rotate(2)를 하면 오른쪽으로 두 칸씩 이동하는 모습을 볼 수 있죠. 하지만 그거 아시나요? deque의 rotate는 음수로도 동작합니다! 그러면 -2를 하면 어떻게 작동을 할까요? 그림에서도 볼 수 있듯이, 왼쪽으로 두 칸씩 이동하여 원래의 q와 같은 모양으로 돌아오게 됩니다. 이처럼, 각각 상하와 좌우를 맡은 row와 column이라는 두 deque으로 주사위의 이동을 구현하겠습니다.

풀이

from collections import deque

dir = [(0,0),(0,1),(0,-1),(-1,0),(1,0)]
move = {1:(0,1), 2:(0,-1), 3:(1,-1), 4:(1,1)}

def getInput():
    # 입력받는 함수
    global N, M, x, y, K, dice, graph, orderlist
    N, M, x, y, K = map(int, input().split())
    dice = [deque([0,0,0,0]), deque([0,0,0,0])]  # 둘 다 마지막이 맨 아래
    graph = [list(map(int, input().split())) for _ in range(N)]
    orderlist = list(map(int, input().split()))
    
def rounding():
    # 주사위를 굴리고 출력하는 함수
    global x, y
    for i in orderlist:
        nx = x+dir[i][0]
        ny = y+dir[i][1]
        
        if 0<=nx<N and 0<=ny<M:
            dice[move[i][0]].rotate(move[i][1])
            dice[1-move[i][0]][1] = dice[move[i][0]][1]
            dice[1-move[i][0]][3] = dice[move[i][0]][3]

            if graph[nx][ny] == 0:
                graph[nx][ny] = dice[0][3]
            else:
                dice[0][3], dice[1][3] = graph[nx][ny], graph[nx][ny]
                graph[nx][ny] = 0
                
            print(dice[0][1])
            x, y = nx, ny


# ===== 실제 실행하는 부분 =====
def main():
    getInput()
    rounding()

main()