본문 바로가기
알고리즘/[python] 백준 BOJ

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

by Alan_Kim 2023. 7. 16.
728x90
반응형

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

 

23288번: 주사위 굴리기 2

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼

www.acmicpc.net

 

 

문제 해결

  • 주사위의 움직임을 어떻게 표현할 것인가?
    • 주사위는 입체로 되어있지만 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
반응형

댓글