백준 23288 : 주사위 굴리기 2

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

23288번: 주사위 굴리기 2

 

1. 주사위 굴리는 것이 핵심!

 처음에는 주사위를 2차원 배열(4 x 4) 로 만들어서 활용하고자 했다. 그렇게 하면 2차원 배열 인덱싱을 실수할 가능성이 있기 때문에, 처음 정의된 주사위의 행과 열을 직접 컨트롤하기로 했다. 다음과 같은 경우를 생각해보자.

초기 상태 주사위에 대해 리스트로 표현하면 위와 같이 정리할 수 있다. 첫 번째 리스트는 주사위의 열에 해당하고(북, 남방향으로 굴릴 때 바뀔 리스트), 두 번째 리스트는 행이다.(동, 서 방향으로 굴릴 때 바뀔 리스트). 초록색 부분은 인덱스가 1인 부분으로 주사위 윗면, 보라색인 부분은 주사위 밑면인 부분으로 인덱스가 3인 부분이다.

 예를 들어 동쪽으로 한 번 굴린다고 해보자. 그러면 아래 리스트는 [6, 4, 1, 3] 이 될 것이고, 위의 리스트는 윗면과 밑바닥 정보만 바뀌게된다([2, 4, 5, 3])

이 상태를 리스트의 append, insert, del을 활용해서 구현해주면 된다. 주사위 사이즈는 정해져있기 때문에 이렇게 해도 문제가 없다. 코드로 구현하면 다음과 같다.

if d == 1 :
    dice_row.insert(0, dice_row[-1])
    del dice_row[-1]
    dice_col[-1] = dice_row[-1]
    dice_col[1] = dice_row[1]

2. 전체코드

 메모리 : 115400 KB, 시간 220 ms, 풀이 시간 : 48 min

N, M, K = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]

dice_row = [4, 1, 3, 6]
dice_col = [2, 1, 5, 6]

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

# 주사위 굴리기 매커니즘
def roll(d):
    # 동, 서
    if d == 1 :
        dice_row.insert(0, dice_row[-1])
        del dice_row[-1]
        dice_col[-1] = dice_row[-1]
        dice_col[1] = dice_row[1]
    if d == 3 :
        dice_row.append(dice_row[0])
        del dice_row[0]
        dice_col[-1] = dice_row[-1]
        dice_col[1] = dice_row[1]
    # 남, 북
    if d == 0 :
        dice_col.append(dice_col[0])
        del dice_col[0]
        dice_row[-1] = dice_col[-1]
        dice_row[1] = dice_col[1]
    if d == 2 :
        dice_col.insert(0, dice_col[-1])
        del dice_col[-1]
        dice_row[-1] = dice_col[-1]
        dice_row[1] = dice_col[1]

def rotate(a, b, d) :
    if a > b :
        return (d + 1) % 4
    if a < b :
        return (d - 1) % 4
    if a == b :
        return d

def reverse(d):
    d += 2
    if d == 5 :
        d = 1
    if d == 4 :
        d = 0
    return d
# 주사위 최족 도착 위치에서 점수 얻기
def bfs(x, y):
    q = [[x, y]]
    B = board[x][y]
    visited = [[False for _ in range(M)] for _ in range(N)]
    visited[x][y] = True
    cnt = 1
    while q :
        x, y = q[0]
        del q[0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] :
                if board[nx][ny] == B :
                    visited[nx][ny] = True
                    cnt += 1
                    q.append([nx, ny])
    return cnt * B

def solve():
    x, y, d = 0, 0, 1
    score = 0
    it = 0
    while True :
        nx = x + dx[d]
        ny = y + dy[d]
        if nx < 0 or nx >= N or ny < 0 or ny >= M :
            d = reverse(d)
            continue
        else :
            roll(d)
            score += bfs(nx, ny)
            d = rotate(dice_row[-1], board[nx][ny], d)
            x, y = nx, ny
            it += 1
        if it == K : break
    return score

print(solve())