[백준 23288] 주사위 굴리기2 Python

푸는데 1시간 정도 걸렸다... 일단 조건이 너무 많아서 생각하기가 내 입장에서는 굉장히 까다로웠다. 그러나 만약 이런 유형으로만 코테가 나온다면 한문제는 풀 수 있을지도,,,

먼저 조건을 정리하자면 다음과 같다.

조건1

주사위 아랫면은 A, 주사위가 있는 칸의 숫자는 B 이며

• A > B 이동방향을 시계방향으로 90도 회전
• A < B 이동방향을 반시계방향으로 90도 회전
• A = B 이동방향의 변화없음

조건2

칸 (x, y)의 점수는 해당 칸에서 연속으로 이동할 수 있는 칸의 개수 X B 와 같다. 이때 DFS를 이용해서 (x, y)에서 연속으로 몇 칸 이동할 수 있는지 세면된다. 이때 이동할 수 있는 칸은 모두 B와 같은 값을 가지면 된다.

조건3

가장 처음에는 주사위의 방향은 동쪽이며 주사위 아랫면은 6이다.

이동횟수만큼 반복문을 돌면서 주사위를 이동시킨다. 이때 사실 주사위의 이동은 별로 어려움이 없다. 하지만 점수 계산이 좀 어려울 수 있는데, (x, y)에서 dfs로 갈 수 있는 칸들에 도달할 때마다 +1 씩 해주면된다.

가장 문제는 왔던 칸으로 되돌아가거나 이미 방문했던 칸을 또 가서 개수를 카운트 할 수 있으므로 방문했던 칸을 기억할 수 있도록 해주면 된다. (나같은경우 그냥 NxM칸의 새배열을 만들어서 방문할때마다 기록했다...)

코드에서 turn은 주사위를 이동시켰을 때 어떤 이동방향인지마다 주사위를 변경시켜주는 메소드이다.

validate는 이동하는 (x,y)칸이 정상적으로 갈 수 있는 칸인지 체크한다.

import sys
r = sys.stdin.readline

def validate(x, y):
    global N, M
    if x < N and x >= 0 and y < M and y >= 0:
        return True
    return False

def turn(cmd):
    global dice
    temp = dice[2]
    if cmd == 0:
        dice[2] = dice[1]
        dice[1] = dice[5]
        dice[5] = dice[3]
        dice[3] = temp
    elif cmd == 1:
        dice[2] = dice[0]
        dice[0] = dice[5]
        dice[5] = dice[4]
        dice[4] = temp
    elif cmd == 2:
        dice[2] = dice[3]
        dice[3] = dice[5]
        dice[5] = dice[1]
        dice[1] = temp
    elif cmd == 3:
        dice[2] = dice[4]
        dice[4] = dice[5]
        dice[5] = dice[0]
        dice[0] = temp

def dfs(depth, x, y, B):
    global maxNum, visit
    maxNum += 1
    visit[x][y] = 1
    # print(x, y, maxNum, depth)
    if validate(x, y+1) and visit[x][y+1] == 0 and matrix[x][y+1] == B:
        dfs(depth + 1, x, y+1, B)
    if validate(x+1, y) and visit[x+1][y] == 0 and matrix[x+1][y] == B:
        dfs(depth + 1, x+1, y, B)
    if validate(x, y-1) and visit[x][y-1] == 0 and matrix[x][y-1] == B:
        dfs(depth + 1, x, y-1, B)
    if validate(x-1, y) and visit[x-1][y] == 0 and matrix[x-1][y] == B:
        dfs(depth + 1, x-1, y, B)
N, M, K = map(int, r().split(" "))

matrix = []

for i in range(N):
    matrix.append(list(map(int, r().split(" "))))

dice = [2, 4, 1, 3, 5, 6]
# go : 진행방향 0: 동, 1: 남, 2: 서, 3:북
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
go = 0
x, y = 0, 0
maxNum = 0
answer = 0
for i in range(K):
    turn(go)
    A = dice[5]
    x = x + move[go][0]
    y = y + move[go][1]

    B = matrix[x][y]
    maxNum = 0

    visit = [[0 for row in range(M)] for col in range(N)]
    dfs(0, x, y, B)
    answer += (maxNum * B)


    if(A > B):
        go = (go + 1) % 4
    elif (A < B):
        if go - 1 < 0:
            go = 3
        else:
            go = go - 1
    if not validate(x + move[go][0], y + move[go][1]):
        go = (go + 2) % 4
print(answer)