[BOJ] 14499. 주사위 굴리기

문제

주사위 굴리기 (https://www.acmicpc.net/problem/14499)

풀이

1. 초기 접근

• 문제조건 해석
  • 역시 삼성 문제는 뭔가 글이 많다.
    • 세세하게 잘 읽어야한다.
    • 두번 세번 읽어줘야 한다. 문제를 잘 읽고 코딩하자.
  • 삼성 문제의 대표적인 시뮬레이션 문제다.
    • 문제에서 주어진 대로 그냥 짜기만 하면 된다.
    • 핵심은, 과연 올바른 자료구조로 잘 구현할 수 있는가? 다.
• 알고리즘
  • 주사위의 각 면을 어떻게 변화시키고 어떻게 각 면에 접근해야할까? 라는 생각이 가장 먼저든다.
  • 먼저 제일 중요해보이는 건, 윗 면과 아랫 면이다. 우리는 이 면에 지속적으로 접근하게 된다.
    • 윗 면과 아랫 면을 고정 인덱스로 두고 접근해야, 덜 복잡할 듯하다.
    • 주사위의 각 면을 고정 인덱스로 두자는 발상이 나오게 된다.
    • 그럼 위, 아래, 앞, 뒤, 오른쪽, 왼쪽을 어떻게 인덱스화 해야할까?
  • 잠시, 주사위가 이동할 때, 각 면이 어떻게 변하는 지 경우를 생각해보자.
    • 위 아래로 이동할 경우, [윗면, 앞면, 아랫면, 뒷면] 에만 영향이 간다.
    • 오른, 왼쪽으로 이동할 경우, [윗면, 오른면, 아랫면, 왼면] 에만 영향이 간다.
    • 가장 직관적인 방법은 주사위의 상태를 두개로 나누어, 바뀔 때마다 윗면, 아랫면만 같도록 만드는 거다.
  • 리스트로 구현해야 하나?
    • 위 같이 구현할 경우, 주사위를 굴리면, 현재 인덱스값이 다음 인덱스값으로 쉬프트 되는 것을 알 수 있다.
    • 예를 들어, 아래(4) 로 굴릴 경우, 윗면 -> 앞면이 되고, 앞면 -> 아랫면이 되는 식이다.
    • 리스트는 쉬프트에 최적화된 자료구조는 아니다. 일반적으로 쉬피트 하면 queue가 떠오른다.
    • 우리에겐 deque가 있다.
      그리고 deque 에는 .rotate() 이 있다.
• 코드

from collections import deque

"""
주사위의 각 면을 고정된 인덱스로 둔다고 생각해보자.
그러면 주사위가 이동할 때마다, 주사위의 해당 면에 해당하는 값들은 바뀌게 된다.
그래서 이렇게 바뀌는 주사위의 상태를 어떤 식으로 담아낼 것인지가 핵심인데,
우리는 한 주사위를 2개의 자료구조로 나눈다.
위 혹은 아래로 굴릴 경우, 오른쪽, 왼쪽면의 값은 바뀌지 않으니, [윗면, 앞면, 아랫면, 뒷면] 만 고려하면 된다. (dice_ud)
오른 혹 왼쪽으로 굴릴 경우, 앞면, 뒷면의 값은 바뀌지 안흥므로, [윗면, 오른면, 아랫면, 왼면] 만 고려하면 된다. (dice_rl)

dice_ud : [윗면, 앞면, 아랫면, 뒷면]
dice_rl : [윗면, 오른면, 아랫면, 왼면]
dice_di : 동, 서, 남, 북으로 움직일 때, deque.rotate() 에 들어갈, 방향을 담는다.
"""
dice_ud = deque([0, 0, 0, 0])
dice_rl = deque([0, 0, 0, 0])
dice_di = [1, -1, -1, 1]
dxs = [0, 0, -1, 1]
dys = [1, -1, 0, 0]

n, m, x, y, k = list(map(int, input().split()))
board = [list(map(int, input().split())) for _ in range(n)]

commands = list(map(int, input().split()))
for command in commands:

    # 다음 이동 좌표의 범위 체크
    nx, ny = x + dxs[command - 1], y + dys[command - 1]
    if nx < 0 or nx >= n or ny < 0 or ny >= m:
        continue
    x, y = nx, ny

    # 이동하는 방향이 위 아래인지, 오른, 왼쪽인지 확인한다.
    if command in [1, 2]:
        direction = dice_di[command - 1]
        dice_rl.rotate(direction)

        # 주사위 상태를 이전에 둘로 나누었으므로, 동기화 시켜줘야 한다. (윗, 아래만 같도록)
        dice_ud[0], dice_ud[2] = dice_rl[0], dice_rl[2]
    elif command in [3, 4]:
        direction = dice_di[command - 1]
        dice_ud.rotate(direction)
        dice_rl[0], dice_rl[2] = dice_ud[0], dice_ud[2]

    # 판에서 이동한 좌표의 값을 보고, 문제에서 시킨걸 한다.
    if board[x][y] == 0:
        board[x][y] = dice_ud[2]
    else:
        dice_ud[2] = dice_rl[2] = board[x][y]
        board[x][y] = 0

    # 윗면을 출력한다.
    print(dice_ud[0])

참고 링크

파이썬 기본 자료구조의 연산 시간복잡도

<https://wiki.python.org/moin/TimeComplexity