[백준-골드3] 23228번 주사위 굴리기2 (구현, BFS, 파이썬)

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

23288번: 주사위 굴리기 2

 

<문제 요약>

- 크기가 N*M 지도가 존재, 주사위를 K번 이동

- 주사위에는 1-6까지 숫자가 적혀있음. 초기 주사위의 이동방향은 동쪽

- 주사위가 이동 방향으로 한칸 굴러감, 만약 이동 방향으로 갔을 때 지도를 이탈한다면 이동 방향을 반대(180도)로

   한 후 움직임

- 주사위가 도착한 칸에 대한 점수를 획득

  - 점수는 해당 칸에서 동서남북으로 이동할만큼 이동, 이 때 해당칸과 숫자가 같은 칸으로만 이동가능

  - 칸에 적힌 정수 B, 이동 가능한 칸 C일때, 점수 = B*C

- 사위의 아랫면에 있는 정수 a와 칸에 있는 정수 b를 비교해서 이동 방향 결정
      # a > b , 시계방향 90도
      # a < b, 반시계 방향 90도
      # a = b, 이동 방향 변화 없음

 

<주사위 회전> - 참고

https://it-hyorim.tistory.com/154

[백준-골드4] 14499번 주사위 굴리기 (구현, 파이썬)

 

<내 코드>

-  rolling_dice(d) : 방향 d로 주사위가 굴러간 후 주사위의 상태를 변화 시킴

- bfs(x,y)

  - 현재 주사위가 있는 위치에서 상,하,좌,우로 칸의 번호가 같은 인접한 칸의 갯수를 파악

- 이동을 k번 반복함

  - 처음 이동할 방향으로 이동을 수행

     - 만약, 범위를 이탈했을 때, 방향을 반대로(180)도 회전해야함. (d+2)%4 이용

     - nx, ny 변경

  - rolling_dice 함수 호출해서 주사위 상태 변화시킴

  - b는 이동한 칸에 적힌 정수, c는 bfs로 인접한칸의 갯수 파악(현재 칸도 포함이므로 cnt=1로 초기화 후 시작)

  - score에 점수를 더해줌

- 방향 재설정

  - 주사위의 바닥에 적힌 숫자와 현재 칸에 적힌 숫자를 비교해서 방향을 변경하거나 유지함

- x, y 업데이트해서 현재 위치 반영

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

n, m, k = map(int, input().split())
maps = []
for _ in range(n):
    maps.append(list(map(int, input().split())))

# 동, 남, 서, 북 순서 -> 시계 방향
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dice = [i for i in range(1,7)] #초기 주사위 칸마다 숫자가 들어 있음
def rolling_dice(d):
    temp = copy.deepcopy(dice)
    if d == 0: #동쪽
        dice[0] = temp[3]
        dice[2] = temp[0]
        dice[3] = temp[5]
        dice[5] = temp[2]

    elif d == 1: #남쪽
        dice[0] = temp[1]
        dice[1] = temp[5]
        dice[4] = temp[0]
        dice[5] = temp[4]

    elif d == 2: #서쪽
        dice[0] = temp[2]
        dice[2] = temp[5]
        dice[3] = temp[0]
        dice[5] = temp[3]

    else: #북쪽
        dice[0] = temp[4]
        dice[1] = temp[0]
        dice[4] = temp[5]
        dice[5] = temp[1]

def bfs(x,y):
    global cnt
    queue = deque()
    queue.append([x,y])
    visited[x][y] = True
    num = maps[x][y]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
                if maps[nx][ny] == num:
                    cnt+=1
                    visited[nx][ny] = True
                    queue.append([nx,ny])
    return cnt

x, y = 0, 0
d = 0
score = 0
for kk in range(k):
    cnt = 1
    visited = [[False]*m for _ in range(n)]

    nx = x + dx[d]
    ny = y + dy[d]

    if not(0<=nx<n and 0<=ny<m): #범위 이탈
        d = (d+2)%4 #반대 방향 회전 (180도)
        nx = x + dx[d]
        ny = y + dy[d]

    rolling_dice(d) #주사위 굴러감
    b = maps[nx][ny]
    c = bfs(nx, ny)
    score += (b*c)

    # 방향 재 설정
    if dice[5] > maps[nx][ny]: #주사위 아랫면 숫자가 해당 칸 보다 클때
        d = (d+1) % 4 # 시계방향 90도 회전
    elif dice[5] < maps[nx][ny]:
        d = (d-1) % 4 # 반시계 방향 90도 회전
    x, y = nx, ny #현재 위치 업데이트

print(score)