백준-5373) 큐빙

1. 문제 링크

백준-3573-P5) 큐빙 (https://www.acmicpc.net/problem/5373)

2. 문제 해석

• $3×3×3$ 칸으로 이루어진 정렬된 큐브에서, N번의 명령(한 면에서 시계 혹은 반시계 방향으로 돌리기)을 수행한 후의 큐브 상태를 구하는 문제이다.

• 1) 입력

  • (1) 테스트케이스 수 (testcase: int)
        (1 <= testcase <= 100)
  • (1) 명령의 수 N: int
        (1 <= N <= 1000)
  • (2) 명령어 "command: str"에 대하여,
        "command ×N"
  
  

• 2) 출력

  • (1) (N회의 명령을 실행한 후 윗면의 정보)×testcase회
  
  

• 3) 풀이 전략

  • (1) 각 면에 따른 큐브의 정보와 인접면 정보를 dict 자료형에 저장한다. (큐브의 정보 기준 기준 위, 오른쪽, 아래, 왼쪽 순서로 저장)
  • (2) 매 테스트케이스 시작마다 큐브를 초기화한다.
  • (3) 큐브를 명령어에 제공된 면을 돌리고, 인접 면의 3개씩을 교체하는 turn 함수를 N회 반복한다.
  • (4) 3을 진행할 때, 해당 명령에서 돌아간 면이 나에게 어느 방향인지에 따라 교체되어야하는 위치를 dict 자료형에 저장하여 교체시 사용한다.

3. 코드

• 1) 작성 코드

  import sys
  
  change_points = dict()  # 돌리는 애를 시계로 돌렸을 때, 인접면 기준 바뀌는 3개의 블럭의 위치를 반환해주는 dict
  change_points.update({0: [(0, 0), (0, 1), (0, 2)]})  # 상단
  change_points.update({1: [(0, 2), (1, 2), (2, 2)]})  # 우측
  change_points.update({2: [(2, 2), (2, 1), (2, 0)]})  # 하단
  change_points.update({3: [(2, 0), (1, 0), (0, 0)]})  # 좌측
  
  def reset():  # 큐브를 최초 상태로 초기화한다.
      global cube
      cube = dict()  # 큐브의 상태를 저장하는 dict
      cube.update({'U': [[['w']*3 for _ in range(3)], "BRFL"]})  # 상단
      cube.update({'D': [[['y']*3 for _ in range(3)], "FRBL"]})  # 하단
      cube.update({'F': [[['r']*3 for _ in range(3)], "URDL"]})  # 앞측
      cube.update({'B': [[['o']*3 for _ in range(3)], "ULDR"]})  # 뒤측
      cube.update({'L': [[['g']*3 for _ in range(3)], "UFDB"]})  # 왼측
      cube.update({'R': [[['b']*3 for _ in range(3)], "UBDF"]})  # 우측
  
  def turn(command: str):  # 들어온 command : "(face)+" or "(face)-" 에 대하여 회전 진행
      face = command[0]  # 회전 위치
      direction = 1 if command[1] == '+' else -1  # '+'는 시계방향 '-'는 반시계 방향
  
      # direction 방향으로 해당 큐브 내부에서 뒤집기
      temp_list = [['0']*3 for _ in range(3)]  # 해당 면을 돌려준 형태를 저장하기 위한 임시 리스트
      refer_list = cube[face][0]  # 가독성을 위해 현재 상태를 가져오기
      for i in range(3):
          for j in range(3):
              if (direction == 1):  # 시계방향으로 돌리는 경우
                  temp_list[i][j] = refer_list[2-j][i]
              else:  # 반 시계방향으로 돌리는 경우
                  temp_list[i][j] = refer_list[j][2-i]
      cube[face][0] = temp_list  # 해당 면을 돌려준 형태로 교체
  
      # 4개 인접면에 방문하며 direction 방향으로 바꿔주기
      next_faces = cube[face][1][::direction]  # 4개의 인접면 복사(시계 혹은 반시계)
      for i in range(5):
          now_face = next_faces[i % 4]  # 방문한 인접면
          adj_dir = cube[now_face][1].index(face)  # now_face 기준 face가 어느 방향인지 얻기
          if (i != 4):  # 현재 자신의 상태를 저장해놓고
              # 돌린 면과 변경할 면을 넣어서 변경할 자리 3개 인자를 빼온다.
              temp = get_temp(now_face, adj_dir)
          if (i != 0):  # 이전에서 받아온 list를 순서대로 넣어준다.
              change(now_face, adj_dir, pre_list)  # 이전에 빼온 인자 3개를 변경할 면에 넣어준다.
          pre_list = temp
      return
  
  def get_temp(now_face: chr, adj_dir: int):
      temp_list = []  # 새로 만들 리스트를 반환하기 위함
      for x, y in change_points[adj_dir]:  # 돌려줄 방향의 위치들에 대하여
          temp_list.append(cube[now_face][0][x][y])  # temp_list에 데이터 추가
      return temp_list  # 변경될 3자리의 정보를 반환
  
  def change(now_face: chr, adj_dir: int, pre_list: list):
      i = 0
      for x, y in change_points[adj_dir]:  # pre_list의 정보를 순차적으로 넣어주기
          cube[now_face][0][x][y] = pre_list[i]
          i += 1
  
  def main():
      testcase = int(sys.stdin.readline().rstrip())  # 테스트케이스 개수
      for _ in range(testcase):
          reset()  # 큐브를 초기화한다.
          n = int(sys.stdin.readline().rstrip())  # 명령의 수 n입력
          commands = sys.stdin.readline().rstrip().split()
  
          for command in commands:  # commands에 대하여 turn 실행
              turn(command)
  
          for three_letters in cube['U'][0]:  # 윗면 출력하기
              for letter in three_letters:
                  print(letter, end="")
              print()
  
  main()
  

• 2) 코드 평가

  • (1) 시간복잡도

    $O(n)$ : $n$회에 걸쳐서 명령을 수행하며, $O(1)$의 작업을 실행하기 때문에, $O(n)$이다.