[BOJ/백준] 23288 주사위 굴리기 2 파이썬

문제 링크 : https://www.acmicpc.net/problem/23288

23288번: 주사위 굴리기 2

 

BFS + 구현 문제이다.

주사위 굴리는게 귀찮은 문제이다.

주사위만 잘 굴리면 어렵지 않게 풀 수 있는 문제이다.

 

나는 주사위를 배열로 할까하다가 dict로 보기 편하게 했다.

 

진행 순서는 다음과 같다.

1. 주사위 굴리기

2. 주사위 회전

3. BFS로 칸 개수 세기

4. 점수 갱신

위의 순서로 k개만큼 반복 하면 된다.

 

 

1. 주사위 굴리기

주어진 전개도 보고 위,아래,왼쪽,오른쪽,상,하 잘 조절해보자.

이때  주어진 맵을 벗어나면 반대로 방향 바꾸고 이동해야한다.

방향도 바뀜을 주의하자.

 

2. 주사위 회전

모듈러 연산으로 쉽게 가자.

시계방향 회전 (d+1)%4

반시계 방향 회전 (d-1)%4

 

3. BFS로 칸 개수 세기

현재 주사위 점에서 시작해서 시작점의 숫자와 같은 숫자를 찾아가자.

BFS로 간단하게 구현가능하다.

 

4. 점수 갱신

3번 단계에서 시작점의 숫자와 개수를 리턴해준다. 이것을 서로 곱해서 점수를 갱신하자.

 

from sys import stdin
from collections import deque

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

input = stdin.readline

n,m,k = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
visited_num = 0

dice = {
    'top':1,
    'bottom':6,
    'up':2,
    'down':5,
    'left':4,
    'right':3
}
def solv():
    x,y = 0,0
    d = 1
    score = 0
    for _ in range(k):
        x,y,d = move_dice(x,y,d)
        d = rotate_dice(x,y,d)
        target, count = count_block(x,y)
        score += target*count

    print(score)

def count_block(sx,sy):
    global visited, visited_num
    visited_num += 1

    target = board[sx][sy]
    visited[sx][sy] = visited_num
    q = deque([(sx,sy)])
    count = 0

    while q:
        x,y = q.pop()
        count += 1

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

            if point_validator(nx,ny) and visited[nx][ny] != visited_num and board[nx][ny] == target:
                visited[nx][ny] = visited_num
                q.appendleft((nx,ny))
    return target, count
def move_dice(x,y,d):
    global dice
    nx = x + dx[d]
    ny = y + dy[d]

    if not point_validator(nx,ny):
        d = (d+2)%4
        nx = x + dx[d]
        ny = y + dy[d]

    if d == 0:
        tmp = dice['top']
        dice['top'] = dice['down']
        dice['down'] = dice['bottom']
        dice['bottom'] = dice['up']
        dice['up'] = tmp
    elif d == 1:
        tmp = dice['top']
        dice['top'] = dice['left']
        dice['left'] = dice['bottom']
        dice['bottom'] = dice['right']
        dice['right'] = tmp
    elif d == 2:
        tmp = dice['top']
        dice['top'] = dice['up']
        dice['up'] = dice['bottom']
        dice['bottom'] = dice['down']
        dice['down'] = tmp
    elif d == 3:
        tmp = dice['top']
        dice['top'] = dice['right']
        dice['right'] = dice['bottom']
        dice['bottom'] = dice['left']
        dice['left'] = tmp
    return nx,ny,d
def rotate_dice(x,y,d):
    A = dice['bottom']
    B = board[x][y]
    if A > B:
        d = (d+1)%4
    elif A < B:
        d = (d-1)%4
    return d
def point_validator(x,y):
    if x < 0 or y < 0 or x >= n or y >= m:
        return False
    return True

solv()