[Python] 백준 23288번: 주사위 굴리기 2

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

23288번: 주사위 굴리기 2

 

 > 풀이

구현만 하면 되는 문제였다. 다음과 같은 사항들을 구현하여 문제를 해결하였다.

 - C의 값들을 담은 grid를 사전에 계산해둔다. BFS로 방문 가능한 같은 숫자인 좌표들을 set에 담고 마지막으로 set을 돌며 set의 length 값을 넣어주었다. 이 때 좌표를 하나의 정수로 인코딩(ex. (2,3) <-> 2*5 + 3 = 13) 하였는데, 이 set을 통해 중복 방문 체크까지 가능하다.

 - 주사위를 굴리는 것을 구현한다. 주사위 전개도를 길이가 6인 리스트에 넣어주었고, 시계 방향, 반시계 방향 계산을 고려하여 전,우,후,좌,상,하 순서로 인덱싱을 하였다. 특히 MOVE_SEQUENCES에 특정 방향으로 이동하였을 때 값이 바뀌어야 하는 순서를 담음으로써 방향에 따른 주사위 전개도의 변화를 쉽게 구현하였다.

 

# -*- coding: utf-8 -*-
import sys
import queue
input = sys.stdin.readline

dx = [1,-1,0,0]
dy = [0,0,1,-1]

FORWARD, RIGHT, BACKWARD, LEFT, TOP, BOTTOM = 0,1,2,3,4,5
POSITION_OFFSETS = [
  [-1,0],[0,1],[1,0],[0,-1]
]      
MOVE_SEQUENCES = [
  [FORWARD,TOP,BACKWARD,BOTTOM],
  [BOTTOM,RIGHT,TOP,LEFT],
  [BOTTOM,BACKWARD,TOP,FORWARD],
  [LEFT,TOP,RIGHT,BOTTOM]
]       
                         
def set_score_grid():
  for i in range(N):
    for j in range(M):
      if(score_grid[i][j] == 0):
        bfs(i, j)            
     
def bfs(start_x, start_y):
  # Get visited
  q = queue.Queue()
  q.put([start_x,start_y])
  visited = set()
  visited.add(start_x*M + start_y) # Encoding position to int

  while(not q.empty()):
    x, y = q.get()                                 

    for k in range(4):
      nx, ny = x + dx[k], y + dy[k]

      if(not (0<=nx<=N-1 and 0<=ny<=M-1)): continue   
      if(grid[x][y] != grid[nx][ny]): continue
      if(nx*M+ny in visited): continue

      q.put([nx,ny])
      visited.add(nx*M + ny)  

  count = len(visited)
  for v in visited:
    x, y = v // M, v % M
    score_grid[x][y] = count

   
def get_score():
  global current_direction
  res = 0
                  
  for _ in range(K):                      
    move_dice(current_direction)

    x, y = current_pos     
    res += score_grid[x][y]*grid[x][y]    

  return res

def move_dice(direction):   
  global current_pos, current_dice, current_direction

  # Set current_pos
  current_pos = get_next_pos(direction)

  # Set current_dice
  tmp = current_dice[MOVE_SEQUENCES[direction][0]]
  for i in range(3):                        
    current_dice[MOVE_SEQUENCES[direction][i]] = current_dice[MOVE_SEQUENCES[direction][i+1]]
  current_dice[MOVE_SEQUENCES[direction][3]] = tmp

  # Set current_pos     
  x, y = current_pos

  A = current_dice[-1]
  B = grid[x][y]

  if(A>B):
    current_direction = (current_direction + 1) % 4
  elif(A<B):
    current_direction = (current_direction + 3) % 4
                                          
  nx, ny = get_next_pos(current_direction)
  if(not (0 <= nx <= N-1 and 0 <= ny <= M-1)):
    current_direction = (current_direction + 2) % 4

def get_next_pos(direction):
  dx, dy = POSITION_OFFSETS[direction]
  return [current_pos[0] + dx, current_pos[1] + dy]

if __name__ == '__main__':
  N, M, K = map(int, input().split())
  grid = [list(map(int, input().split())) for _ in range(N)]      

  score_grid = [[0]*M for _ in range(N)]
  set_score_grid()   
                          
  current_pos = [0,0]
  current_direction = RIGHT
  current_dice = [2,3,5,4,1,6]
  print(get_score())