백준 23288 : 주사위 굴리기 2 (Python)

본문 링크

import sys
input=sys.stdin.readline
from collections import deque

L_I=lambda:list(map(int,input().split()))
I_S=lambda:map(int,input().split())
dx=[-1,1,0,0]
dy=[0,0,-1,1]
"""
Move 1 : 동 , 2: 서  , 3:남 , 4:북
"""

def BFS(x,y):

    Q=deque()
    Q.append([x,y])
    visit=[ [False]*M for _ in range(N) ]
    visit[x][y] = True
    check = graph[x][y] ;  count = 1

    while Q:
        x,y=Q.popleft()

        for i in range(4):
            nx=x+dx[i] ; ny=y+dy[i]

            if 0<=nx<N and 0<=ny<M and not visit[nx][ny] and graph[nx][ny]==check:
                visit[nx][ny]=True
                Q.append([nx,ny])
                count+=1

    return count*check

def Dice():

    global N,M,K
    breath=deque([4,1,3])
    high=deque([2,1,5,6])
    Move = 1 ; x,y=[0,0]
    total = 0

    while K:
        if Move==1:
            if y==M-1: # 반대 방향
                Move=2
                y-=1
                breath[0], high[1], breath[2], high[3] = high[1], breath[2], high[3], breath[0]
            else:
                y+=1
                breath[0], high[3], breath[2], high[1] = high[3], breath[2], high[1], breath[0]

        elif Move==2:
            if y==0:
                Move=1
                y+=1
                breath[0], high[3], breath[2], high[1] = high[3], breath[2], high[1], breath[0]
            else:
                y-=1
                breath[0], high[1], breath[2], high[3] = high[1], breath[2], high[3], breath[0]
        elif Move==3:
            if x==N-1:
                Move=4
                x-=1
                high.append(high.popleft())
                breath[1] = high[3]
            else:
                x += 1
                high.appendleft(high.pop())
                breath[1] = high[3]
        else:
            if x==0:
                x+=1
                Move=3
                high.appendleft(high.pop())
                breath[1] = high[3]
            else:
                x -= 1
                high.append(high.popleft())
                breath[1] = high[3]

        if high[3]>graph[x][y]: # 이동 방향을 90도 시계 방향으로 회전시킨다.
            if Move==1:
                Move=3
            elif Move==2:
                Move=4
            elif Move==3:
                Move=2
            else:
                Move=1
        elif high[3]<graph[x][y]: #A < B인 경우 이동 방향을 90도 반시계 방향으로 회전시킨다.
            if Move==1:
                Move=4
            elif Move==2:
                Move=3
            elif Move==3:
                Move=1
            else:
                Move=2
        K-=1

        total += BFS(x,y)
    return total




N,M,K=I_S()

graph=[ L_I() for _ in range(N) ]

print(Dice())

📌 어떻게 접근할 것인가?

어제 주사위굴리기 문제를 풀고 보니깐 2번째 시리즈 문제도 있어서 오늘 풀었습니다.

다만 다른점은 주사위의 밑면과 윗면이 바뀌었다는 점이고 문제내용이 많이 다릅니다.

처음에는 예제가 정말 이해안됬는데 , 처음 오른쪽으로 간 후에 , 1 이라는 지점을 만나면
BFS 를 통해 상하좌우로 1이랑 같은 지점을 탐색해서

1 × ( BFS 시 같은 수의 개수 )

이 값이 추가점수가 되고 $K$ 는 상하좌우로 주사위의 이동횟수를 나타내었습니다.
문제를 이해하고 나면 BFS 부분은 그냥 함수로 구현해주면 되고

Move 변수를 통해 주사위의 바닥과 그래프의 값에 따라 방향이 바뀌는걸 구현해주었습니다.

• breath=deque([4,1,3]) , high=deque([2,1,5,6])

주사위굴리기 1 문제에서 처럼 주사위 도면을 가로와 세로에 대해서 리스트를 만들어 주었고

"""
동쪽 - breath[0], high[3], breath[2], high[1] = high[3], breath[2], high[1], breath[0]
서쪽 - breath[0], high[1], breath[2], high[3] = high[1], breath[2], high[3], breath[0]
남쪽 - high.appendleft(high.pop()) ; breath[1] = high[3]
북쪽 - high.append(high.popleft()) ; breath[1] = high[3]
"""

위 조건을 사용했습니다. 이는 주사위를 동서남북으로 이동했을때 도면에 대한 변화입니다.

주사위굴리기1 에서는 breath[1]=high[1] 로 했지만 현재 바닥은 high[3] 이기 때문에 breath[1] = high[3] 로 고쳐주었습니다.

또한 이동시에 그래프의 밖으로 나갈수 있기 때문에 매번 이동하기 전에 범위를 체크해준 후에
만약 그래프 밖으로 나갈수 있다면 반대방향으로 이동해주었습니다.

동서남북으로 이동할때 도면의 변화가 이해가안된다면 직접 주사위를 굴러보는것도 괜찮을것 같습니다. 처음에 주사위 없이 머리속으로 도면의 변화를 생각하는데 좀 오래걸렸던것 같았습니다.