import sys
input = sys.stdin.readline
from collections import deque
dy = [1,0,-1,0]
dx = [0,1,0,-1]
def roll(d):
newdice = dice[:]
if d == 0:
for i in range(4):
newdice[(i-1)%4] = dice[i]
elif d == 1:
newdice[0] = dice[5]
newdice[5] = dice[2]
newdice[2] = dice[4]
newdice[4] = dice[0]
elif d == 2:
for i in range(4):
newdice[(i+1)%4] = dice[i]
else:
newdice[5] = dice[0]
newdice[2] = dice[5]
newdice[4] = dice[2]
newdice[0] = dice[4]
return newdice
def BFS(y,x,n):
cnt = 0
dq = deque()
dq.append((y,x))
co = []
while dq:
y,x = dq.popleft()
if visited[y][x]:
continue
visited[y][x] = 1
cnt += 1
co.append((y,x))
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0:
if board[y1][x1] == n:
dq.append((y1,x1))
for y,x in co:
score[y][x] = n*cnt
N,M,K = map(int,input().split())
board = []
for i in range(N):
board.append([*map(int,input().split())])
score = [[0]*M for i in range(N)]
visited = [[0]*M for i in range(N)]
for y in range(N):
for x in range(M):
if visited[y][x]:
continue
BFS(y,x,board[y][x])
dice = [6,5,1,2,4,3]
y = x = 0
d = 1
result = 0
for i in range(K):
y1,x1 = y+dy[d],x+dx[d]
if not (N>y1>=0 and M>x1>=0):
d = (d+2)%4
y1,x1 = y+dy[d],x+dx[d]
y,x = y1,x1
dice = roll(d)
result += score[y][x]
if dice[0] > board[y][x]:
d = (d-1)%4
elif dice[0] < board[y][x]:
d = (d+1)%4
print(result)
쉬운 구현문제
알고리즘을 요약하면,
1. BFS 탐사로 각 좌표의 점수를 기록한다
2. 주사위를 list로 만든 후 동서남북 각 방향에 대해 굴리면 바뀌는 방식을 함수로 만든다
3. 결과 출력
주사위를 굴리는 함수를 만들 때 방향이나 이런게 헷갈려서 틀릴 수도 있는데 예제가 친절해서 쉽게 디버깅할 수 있다.
오늘의 교훈) 구현은 쉽고 재미없다