[코드트리/삼성SW역량테스트] 정육면체 한번 더 굴리기 (python)

Problem : https://www.codetree.ai/training-field/frequent-problems/problems/cube-rounding-again

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

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:23:10

 

---

 

문제 설명 / 입력 및 출력

 

 

자세한 설명은 코드트리 사이트 링크를 참조해 주세요!

 

 

---

 

풀이

 

주사위형 구현 문제.

 

* 스코어 변동이 아예 없으므로 좌표당 얻을 수 있는 스코어를 미리 구해 두면 효율적이다.

* 주사위는 4 x 3 행렬로 구현하여 상하좌우 이동시 처리를 간단하게 구현할 수 있다.

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
score_maps = [[0]*n for _ in range(n)]
score_visited = [[False]*n for _ in range(n)]
d = 0
ans = 0

dice_coord = (0, 0)
dice = [
    [ 0, 5, 0],
    [ 4, 1, 3],
    [ 0, 2, 0],
    [ 0, 6, 0]
]

def init() :
    for i in range(n) :
        for j in range(n) :
            if not score_visited[i][j] :
                score_bfs(i, j, maps[i][j])

def score_bfs(r, c, num) :
    q = deque([(r, c)])
    coord_list = [(r, c)]
    score_visited[r][c] = True
    cnt = 1
    while q :
        r, c = q.popleft()
        for i in range(4) :
            ar, ac = r + dr[i], c + dc[i]
            if -1 < ar < n and -1 < ac < n and not score_visited[ar][ac] and maps[ar][ac] == num :
                score_visited[ar][ac] = True
                coord_list.append((ar, ac))
                cnt += 1
                q.append((ar, ac))
    for r, c in coord_list :
        score_maps[r][c] = num * cnt

def dice_move() :
    global d, dice_coord, ans
    r, c = dice_coord
    if not ( -1 < r + dr[d] < n and -1 < c + dc[d] < n) :
        d = (d+2) % 4
        dice_move()
        return
    r += dr[d]
    c += dc[d]
    if d == 0 :
        dice[1][0], dice[1][1], dice[1][2], dice[3][1] = dice[3][1], dice[1][0], dice[1][1], dice[1][2]
    elif d == 2 :
        dice[1][0], dice[1][1], dice[1][2], dice[3][1] = dice[1][1], dice[1][2], dice[3][1], dice[1][0]
    elif d == 1 :
        dice[0][1], dice[1][1], dice[2][1], dice[3][1] = dice[3][1], dice[0][1], dice[1][1], dice[2][1]
    else :
        dice[0][1], dice[1][1], dice[2][1], dice[3][1] = dice[1][1], dice[2][1], dice[3][1], dice[0][1]
    ans += score_maps[r][c]
    dice_coord = (r, c)

    if dice[3][1] > maps[r][c] :
        d = (d + 1) % 4
    elif dice[3][1] < maps[r][c] :
        d = (d - 1) % 4


init()
for _ in range(m) :
    dice_move()
print(ans)

풀이 완료!