1.아이디어
주사위의 움직임에 집중해서 설명한다. 나머지 조건은 어렵지 않으므로 생략한다. 주사위는 아래와 같이 2차원 배열로 표현한다.
"""
dice[0][1] == 뒷면
dice[1][0] == 좌측면
dice[1][1] == 윗면
dice[1][2] == 우측면
dice[2][1] == 앞면
dice[3][1] == 밑면
"""
dice = [
[0,2,0],
[4,1,3],
[0,5,0],
[0,6,0]
]여기서 밑면은 dice[3][1]이다. 주사위를 만들었으니 주사위를 동서남북으로 움직여보자.
동쪽방향
주사위를 동쪽 방향으로 움직이면 주사위 윗면이 우측면으로, 우측면은 밑면으로, 밑면은 좌측면으로 좌측면은 윗면으로 이동한다. 앞면과 뒷면은 그대로이다. 이를 코드로 표현하면 다음과 같다.
tmp = dice[1][2]
for i in range(2, 0, -1): dice[1][i] = dice[1][i-1]
dice[1][0] = dice[3][1]
dice[3][1] = tmp서쪽방향
주사위를 서쪽방향으로 이동하면 윗면이 좌측면으로, 좌측면은 밑면으로, 밑면은 우측면으로, 우측면은 윗면으로 이동한다. 이를 코드로 표현하면 다음과 같다.
tmp = dice[1][0]
for i in range(0, 2): dice[1][i] = dice[1][i+1]
dice[1][2] = dice[3][1]
dice[3][1] = tmp북쪽방향
주사위를 북쪽방향으로 이동하면, 윗면은 뒷면으로 뒷면은 밑면으로, 밑면은 앞면으로 앞면은 윗면으로 이동한다. 좌측면과 우측면은 그대로이다. 이를 코드로 표현하면 다음과 같다.
tmp = dice[0][1]
for i in range(0, 3): dice[i][1] = dice[i+1][1]
dice[3][1] = tmp남쪽방향
주사위를 남쪽방향으로 이동하면, 앞면은 밑면으로, 밑면은 뒷면으로, 뒷면은 윗면으로, 윗면은 앞면으로 이동한다. 좌측면과 우측면은 그대로이다. 이를 코드로 표현하면 다음과 같다.
tmp = dice[3][1]
for i in range(3, 0, -1): dice[i][1] = dice[i-1][1]
dice[0][1] = tmp주사위 이동을 구현했으면 나머지는 조건에 따라 구현해주면된다.
2.코드
from collections import deque
NORTH = 0
EAST = 1
SOUTH = 2
WEST = 3
r, c, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(r)]
d = ((-1,0), (0,1), (1,0), (0,-1))
dice = [
[0,2,0],
[4,1,3],
[0,5,0],
[0,6,0]
]
def move_dice(to):
if to == NORTH:
tmp = dice[0][1]
for i in range(0, 3): dice[i][1] = dice[i+1][1]
dice[3][1] = tmp
elif to == EAST:
tmp = dice[1][2]
for i in range(2, 0, -1): dice[1][i] = dice[1][i-1]
dice[1][0] = dice[3][1]
dice[3][1] = tmp
elif to == SOUTH:
tmp = dice[3][1]
for i in range(3, 0, -1): dice[i][1] = dice[i-1][1]
dice[0][1] = tmp
elif to == WEST:
tmp = dice[1][0]
for i in range(0, 2): dice[1][i] = dice[1][i+1]
dice[1][2] = dice[3][1]
dice[3][1] = tmp
def isin(y, x):
if -1<y<r and -1<x<c: return True
return False
def move(y, x, to):
ny = y + d[to][0]
nx = x + d[to][1]
if not isin(ny, nx):
if to == EAST: to = WEST
elif to == WEST: to = EAST
elif to == NORTH: to = SOUTH
elif to == SOUTH: to = NORTH
ny = y + d[to][0]
nx = x + d[to][1]
move_dice(to)
return ny, nx, to
def get_next_direction(sy, sx, to):
if arr[sy][sx] > dice[3][1]: return to-1 if to > 0 else WEST
elif arr[sy][sx] < dice[3][1]: return (to+1) % 4
return to
def get_score(sy, sx):
q = deque()
visited = [[False]*c for _ in range(r)]
q.append((sy,sx))
visited[sy][sx] = True
cnt = 1
while q:
y, x = q.popleft()
for dy, dx in d:
ny = y + dy
nx = x + dx
if not isin(ny, nx): continue
if not visited[ny][nx] and arr[ny][nx] == arr[sy][sx]:
visited[ny][nx] = True
cnt += 1
q.append((ny,nx))
return cnt
to = EAST
y, x = 0, 0
answer = 0
while k:
y, x, to = move(y, x, to)
answer += get_score(y, x) * arr[y][x]
to = get_next_direction(y, x, to)
k -= 1
print(answer)