[코드트리] - 정육면체 한번 더 굴리기

https://www.codetree.ai/training-field/frequent-problems/problems/cube-rounding-again/description?page=1&pageSize=20 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제종류

dx dy technique, bfs, simulation

풀이시간

설계:30분 구현:50분

풀이방법

문제에서 설명하는 정육면체는 반대편의 숫자와의 합이 7인 형태로, 주사위와 같은 형태다.

특정 턴의 주사위의 상태정보 (바라보고 있는 면, 값)을 갱신하고 점수는 BFS 탐색을 통해 매번 더해주면된다.

코드

from collections import deque

# 오 위 왼 아
dx, dy = [0, -1, 0, 1], [1, 0, -1, 0]
# 주사위
dice = {
    'U': 1,
    'R': 3,
    'F': 2
}


def get_next_dict_info(d):
    # 오 위 왼 아
    # dict
    dice_roll = {
        0: [('U', 7 - dice['R']), ('R', dice['U'])],
        1: [('U', dice['F']), ('F', 7 - dice['U'])],
        2: [('U', dice['R']), ('R', 7 - dice['U'])],
        3: [('F', dice['U']), ('U', 7 - dice['F'])],
    }
    return dice_roll[d]


def in_range(x, y, n):
    return 0 <= x < n and 0 <= y < n


def get_score(x, y, arr):
    ret = 0
    n = len(arr)
    chk = [[0] * n for i in range(n)]
    tar = arr[x][y]
    q = deque([])
    q.append((x, y))
    while len(q):
        fx, fy = q.popleft()
        if chk[fx][fy]:
            continue
        chk[fx][fy] = 1
        ret += 1
        for ddx, ddy in zip(dx, dy):
            nx, ny = fx + ddx, fy + ddy
            if in_range(nx, ny, n) and not chk[nx][ny] and arr[nx][ny] == tar:
                q.append((nx, ny))

    return ret * tar


def trans_d(d):
    if d < 0:
        return 3
    if d > 3:
        return 0
    return d


def main():
    ans = 0
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]

    cx, cy, cd = 0, 0, 0

    for turn in range(M):
        nx, ny = cx + dx[cd], cy + dy[cd]

        # 만약 격자 밖이면 방향 반대로함
        if not in_range(nx, ny, N):
            cd ^= 2
            nx, ny = cx + dx[cd], cy + dy[cd]
        cx, cy = nx, ny
        # 주사위 정보 체인지
        next_dice_info = get_next_dict_info(cd)
        for key, next_val in next_dice_info:
            dice[key] = next_val
        # 주사위 방향 바꾸기
        down_val = 7 - dice['U']
        if arr[cx][cy] < down_val:
            # 시게
            cd = trans_d(cd - 1)
        if arr[cx][cy] > down_val:
            cd = trans_d(cd + 1)
        # 정답에 더하고
        ans += get_score(cx, cy, arr)

    print(ans)


main()