문제

BOJ 23288: 주사위 굴리기 2 https://www.acmicpc.net/problem/23288

풀이

조건

• 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다.
• 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있는 칸의 좌표는 (N, M)이다.
• 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 각 면에는 1보다 크거나 같고, 6보다 작거나 같은 정수가 하나씩 있다.
• 주사위 한 면의 크기와 지도 한 칸의 크기는 같다.
• 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (1, 1) 이다.
• 주사위의 이동 한 번은 다음과 같은 방식으로 이루어진다.
  1. 주사위가 이동 방향으로 한 칸 굴러간다. 만약, 이동 방향에 칸이 없다면, 이동 방향을 반대로 한 다음 한 칸 굴러간다.
     • 이동 방향을 반대로 할 땐 횟수에 추가하지 않는다.
  2. 주사위가 도착한 칸 (x, y)에 대한 점수를 획득한다.
  3. 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸 (x, y)에 있는 정수 B를 비교해 이동 방향을 결정한다.
  • A > B인 경우 이동 방향을 90도 시계 방향으로 회전시킨다.
  • A < B인 경우 이동 방향을 90도 반시계 방향으로 회전시킨다.
  • A = B인 경우 이동 방향에 변화는 없다.
• (x, y)에 있는 정수를 B라고 했을때, (x, y)에서 동서남북 방향으로 연속해서 이동할 수 있는 칸의 수 C를 모두 구한다. 이때 이동할 수 있는 칸에는 모두 정수 B가 있어야 한다. 여기서 점수는 B와 C를 곱한 값이다.

풀이 순서

• 입력받은 횟수(K) 만큼 반복하며 점수를 구한다.
• 현재 주사위의 방향에 맞춰 새로운 주사위의 위치를 구하고 주사위를 굴린다.
  • 주사위를 굴릴 땐 크기가 6인 배열을 사용해 굴린 상태를 기록하여 구한다.
• 해당 위치가 유효한 위치라면 4방향 탐색을 통해 점수를 구한다.
• 주사위의 새로운 방향을 구한다.

코드

Python

import sys
from collections import deque


def roll_dice(dice, direction):
    n_dice = [0] * 6
    # 동, 남, 서, 북 순으로 굴림
    if direction == 0:
        n_dice[0] = dice[3]
        n_dice[1] = dice[1]
        n_dice[2] = dice[0]
        n_dice[3] = dice[5]
        n_dice[4] = dice[4]
        n_dice[5] = dice[2]
    elif direction == 1:
        n_dice[0] = dice[1]
        n_dice[1] = dice[5]
        n_dice[2] = dice[2]
        n_dice[3] = dice[3]
        n_dice[4] = dice[0]
        n_dice[5] = dice[4]
    elif direction == 2:
        n_dice[0] = dice[2]
        n_dice[1] = dice[1]
        n_dice[2] = dice[5]
        n_dice[3] = dice[0]
        n_dice[4] = dice[4]
        n_dice[5] = dice[3]
    elif direction == 3:
        n_dice[0] = dice[4]
        n_dice[1] = dice[0]
        n_dice[2] = dice[2]
        n_dice[3] = dice[3]
        n_dice[4] = dice[5]
        n_dice[5] = dice[1]
    return n_dice


#  동, 남, 서, 북
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

N, M, K = map(int, sys.stdin.readline().rstrip().split())

board = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]
answer = 0

now_dice = [1, 2, 3, 4, 5, 6]
now_dice_x = 0
now_dice_y = 0
now_dir = 0

turn = 0
while turn < K:
    # 주사위 굴러감
    new_dice_x = now_dice_x + dx[now_dir]
    new_dice_y = now_dice_y + dy[now_dir]

    if new_dice_x < 0 or new_dice_y < 0 or new_dice_x >= N or new_dice_y >= M:
        now_dir = (now_dir + 2) % 4
        continue

    turn += 1

    new_dice = roll_dice(now_dice, now_dir)
    # 굴러간 자리 기준으로 동서남북 탐색해서 해당 위치에서의 점수 구함
    que = deque()
    is_visited = [[False for _ in range(M)] for _ in range(N)]

    que.append([new_dice_x, new_dice_y])
    is_visited[new_dice_x][new_dice_y] = True
    cnt = 1
    while que:
        now_x, now_y = que.popleft()

        for t in range(4):
            n_x = now_x + dx[t]
            n_y = now_y + dy[t]

            if n_x < 0 or n_y < 0 or n_x >= N or n_y >= M:
                continue
            if is_visited[n_x][n_y] or board[n_x][n_y] != board[new_dice_x][new_dice_y]:
                continue
            que.append([n_x, n_y])
            is_visited[n_x][n_y] = True
            cnt += 1
	# 점수를 구하고 더함
    answer += cnt * board[new_dice_x][new_dice_y]
    # 방향 다시 맞춤
    if board[new_dice_x][new_dice_y] < new_dice[5]:
        now_dir = (now_dir + 1) % 4
    elif board[new_dice_x][new_dice_y] > new_dice[5]:
        now_dir = now_dir - 1
        if now_dir < 0:
            now_dir = 3
	
    # 다음 반복문에 사용하기 위해 변수 갱신
    now_dice_x = new_dice_x
    now_dice_y = new_dice_y
    now_dice = new_dice
    # 반복

print(answer)

정리

• 반복문을 돌릴 때 새로 구한 상태를 다음 상태에 사용할 변수에 갱신해주지 않아 시간 낭비를 했다.