728x90
반응형
https://www.acmicpc.net/problem/23288
문제 해결
- 주사위의 움직임을 어떻게 표현할 것인가?
- 주사위는 입체로 되어있지만 1, 2, 3, 4, 5, 6면이 있다는 것을 알고 있다. 따라서 일차원 배열로 1면 ,2면,3면,4면,5면,6면을 [1,2,3,4,5,6]으로 나타내고 먄약 1면과 3면이 바뀌었으면 dice[0], dice[3] = dice[3],dice[0] 이렇게 바꾸는 것이 편하다.
- 점수를 계산하는 방법은 같은 숫자가 있는 이어지는 최대 넓이를 구하면 되는 것이므로 bfs를 쓰면 쉽게 구할 수 있다.
CODE
import sys
input = sys.stdin.readline
from collections import deque
def bfs(sx,sy,num):
visited[sx][sy] = 1
que.append((sx,sy))
cnt = 1
while que:
r, c = que.popleft()
for i in range(4):
nr, nc = r + dxs[i], c + dys[i]
if 0<=nr<N and 0<=nc<M:
if visited[nr][nc] ==0 and board[nr][nc] ==num:
cnt += 1
visited[nr][nc] = 1
que.append((nr,nc))
return cnt
if __name__=='__main__':
N, M, K = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
dxs = [0,1,0,-1]
dys = [1,0,-1,0]
dice = [1, 2, 3, 4, 5, 6]
dir = 0
x, y = 0, 0
answer = 0
for idx in range(K):
if not 0<=x+dxs[dir]<N or not 0<=y+dys[dir]<M:
dir = (dir+2)%4
x, y = x + dxs[dir] , y+dys[dir]
que = deque()
visited = [[0]*M for _ in range(N)]
answer += (bfs(x,y,board[x][y]))*board[x][y]
if dir ==0:
dice[0], dice[2],dice[3],dice[5] = dice[3],dice[0],dice[5],dice[2]
elif dir == 1:
dice[0], dice[1], dice[4], dice[5] = dice[1], dice[5], dice[0], dice[4]
elif dir == 2:
dice[0], dice[2], dice[3], dice[5] = dice[2], dice[5], dice[0], dice[3]
else:
dice[0], dice[1], dice[4], dice[5] = dice[4], dice[0], dice[5], dice[1]
if dice[5]>board[x][y]:
dir = (dir+1)%4
elif dice[5] < board[x][y]:
dir = (dir-1)%4
print(answer)
728x90
반응형
'알고리즘 > [python] 백준 BOJ' 카테고리의 다른 글
[python] 백준 17616 등수 찾기 (0) | 2023.08.11 |
---|---|
[python] 백준 5615 아파트 임대 (0) | 2023.07.31 |
[python] 백준 1431 시리얼 번호 (0) | 2023.07.11 |
[python] 백준 3986 좋은 단어 (0) | 2023.07.10 |
[python] 백준 21610 마법사 상어와 비바라기 (0) | 2023.07.09 |
댓글