[백준] 23288. 🎲주사위 굴리기 2 (파이썬)

문제

주사위 굴리기2

🎲주사위의 이동에서 획득한 점수의 합을 구해보자.

시간 제한 2초
메모리 제한 1024MB

• 지도의 크기 N x M 
• 주사위 존재, 각 면에는 1 ~ 6까지의 수 중 하나가 써 있음.
• 주사위 한 면의 크기와 지도 한 칸의 크기는 같다.
• 초기 상태 
  • 주사위는 지도 위 (1, 1) 위치에 놓여 있다.
  • 주사위는 윗면이 1, 오른쪽 면이 3인 상태로 놓여 있다.
• 주사위의 이동
  1. 이동 방향으로 한 칸 굴러간다 / 이동 방향에 칸이 없다면, 이동 방향을 반대 방향으로 전환
  2. 도착한 칸의 점수를 획득한다.
  3. 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸에 적힌 정수 B를 비교하여 다음 이동 방향을 결정한다.
     1.  A < B : 이동 방향을 반시계 방향으로 90' 회전
     2.  A > B : 이동 방향을 시계 방향으로 90' 회전
     3.  A = B : 변화 없음.

• 점수 획득 방법
  
  • 칸(x,y)에 있는 정수를 B라고 할때, 해당 칸과 동서남북으로 연속해서 이동할 수 있는 칸 수 C를 구한다.
  • 이때 이동할 수 있는 칸에는 정수 B가 있어야 한다.
  • 획득 가능한 점수는 B와 C를 곱한 값이다.
• 이동 횟수 K가 주어졌을때, 각 이동에서 획득한 점수의 합을 구해보자.

---

풀이

 

핵심 알고리즘

알고리즘은 정말 간단하다.

0. 주사위의 상태를 1차원 배열에 나타내고, 각 index가 주사위의 어느 면을 가리키는지 정해 준다.
본 게시글에서는 dice = [윗면, 북, 동, 남, 서, 아랫면] 순으로 정하고 진행합니다!

1. 주사위🎲를 이동 방향으로 굴린다. -> roll_dice() -> 직접 구현하기!!
2. 주사위가 도착한 칸의 점수를 획득 -> get_score() -> BFS or DFS
3. 다음 주사위의 이동 방향 결정 -> next_dir()

위 과정을 이동 횟수 k만큼 반복한다.

1. 주사위를 굴리면 주사위에선 어떤 일이 일어날까 ?? 1차원 배열상에서 회전 구현

이를 구현하는 것이 이 문제의 가장 핵심이 아닐까 싶다!
이러한 유형은 삼성 문제에서 자주 출제되며, 큐브의 회전을 다룬 큐빙 문제도
좀 더 복잡하지만 동일한 로직을 이용하기 때문에 꼭 풀어보셨으면 좋겠다.


**주사위의 초기 상태

   1                     북
4 0 2 5 => 서 윗면 동 아랫면
   3                     남


주사위는 동, 서, 남, 북 4방향으로 이동 가능하므로, 하나씩 살펴보자.

 

1. 동(→)쪽으로 이동하는 경우

좌우 이동의 경우에는 윗면 아랫면을 포함하여 서쪽 면, 동쪽 면을 이동시킨다.

   1                     북
4 0 2 5 => 서 윗면 동 아랫면
   3                     남


동쪽으로 이동 후 모습↓

   1                       북
5 4 0 2 => 아랫면 서 윗면 동
   3                       남


서, 윗면, 동, 아랫면 부분이 한 칸씩 동쪽으로 이동한 모습이다.
코드로 나타내면 다음과 같다.

    if d == 0: # 동
        tmp = dice[2] # 동쪽 저장   
        dice[2] = dice[0] # 동쪽이 있던 자리에 윗면 값 저장
        dice[0] = dice[4] # 윗면이 있던 자리에 서쪽 값 저장 
        dice[4] = dice[5] # 서쪽이 있던 자리에 아랫면 값 저장
        dice[5] = tmp # 아랫면이 있던 자리에, tmp(동쪽) 저장

회전시킬 면들 중 임의의 면 하나를 지정하고(동)
tmp변수를 이용하여
값을 옮겨주는 방식으로 회전시킬 수 있다.

그렇다면 서쪽은 어떨까?


2. 서(←)쪽으로 이동하는 경우

   1                    북
0 2 5 4 => 서 윗면 동 아랫면
   3                    남


서쪽으로 이동 후 모습↓

   1                    북
0 2 5 4 => 윗면 동 아랫면 서
   3                    남


주사위가 동쪽으로 이동하는 경우에서 정반대로 진행해주면 된다.

    elif d == 2: # 서
        tmp = dice[4] # 서쪽 저장
        dice[4] = dice[0] # 서쪽이 있던 자리에, 윗면 저장
        dice[0] = dice[2] # 윗면이 있던 자리에, 동쪽 저장
        dice[2] = dice[5] # 동쪽이 있던 자리에, 아랫면 저장
        dice[5] = tmp # 아랫면이 있던 자리에, tmp(서쪽) 저장

3. 남(↓) 쪽으로 이동하는 경우

상하 이동의 경우에는 좌우 이동과 달리 윗면 아랫면을 포함하여 북쪽 면, 남쪽 면을 이동시킨다.

   1                     북
0 2 5 4 => 서 윗면 동 아랫면
   3                     남


남쪽으로 이동 후 모습↓

   1              아랫면
0 2 5 4 => 동 북 서 남
   3               윗면


코드로 구현하면 다음과 같다.

    elif d == 1: # 남
        tmp = dice[3] # 남쪽 저장
        dice[3] = dice[0] # 남쪽이 있던 자리에, 윗면 저장
        dice[0] = dice[1] # 윗면이 있던 자리에, 북쪽 저장
        dice[1] = dice[5] # 북쪽이 있던 자리에, 아랫면 저장
        dice[5] = tmp # 아랫면이 있던 자리에, 남쪽 저장

4. 북(↑) 쪽으로 이동하는 경우

   1                     북
0 2 5 4 => 서 윗면 동 아랫면
   3                     남


북쪽으로 이동 후 모습↓

   1                윗면
0 2 5 4 => 동 남 서 북
   3              아랫면

    elif d == 3: #북
        tmp = dice[1] # 북쪽 저장
        dice[1] = dice[0] # 북쪽이 있던 자리에, 윗면 저장
        dice[0] = dice[3] # 윗면이 있던 자리에, 남쪽 저장
        dice[3] = dice[5] # 남쪽이 있던 자리에, 아랫면 저장
        dice[5] = tmp # 아랫면이 있던 자리에, 북쪽 저장

 

2. 주사위가 도착한 칸의 점수 획득 - > BFS

앞서 적어둔 점수 획득 방법의 조건은 다음과 같았다.

• 점수 획득 방법
  
  • 칸(x,y)에 있는 정수를 B라고 할때, 해당 칸과 동서남북으로 연속해서 이동할 수 있는 칸 수 C를 구한다.
  • 이때 이동할 수 있는 칸에는 정수 B가 있어야 한다.
  • 획득 가능한 점수는 B와 C를 곱한 값이다.

아래 코드에서는 주사위가 도착한 칸에 있는 정수를 변수 value에 저장하고,
C를 구하기 위해 인접한 칸에서 BFS를 진행하도록 했다.

# 점수 획득을 위해 BFS 실행
def get_score(i, j):
    global dir

    cnt = 1
    value = board[i][j] # B
    visited = [[0 for _ in range(m)] for _ in range(n)]

    visited[i][j] = 1

    q = deque()
    q.append((i, j))

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

        for i in range(4):
            nx = x + dir[i][0]
            ny = y + dir[i][1]

            if in_range(nx, ny):
                if not visited[nx][ny] and board[nx][ny] == value: # 아직 미방문, 같은 정수를 가진 칸
                    visited[nx][ny] = 1
                    q.append((nx, ny))
                    cnt += 1

    return value * cnt

역시나 DFS로도 구현 가능하다.

 

 

최종 코드

from collections import deque
import sys

input = sys.stdin.readline

'''
풀이 방법 : 구현 + DFS
시간 복잡도 : O(N^2)
공간 복잡도 : O(N^2)

1. 주사위🎲를 이동 방향으로 굴린다. -> roll_dice()
2. 주사위가 도착한 칸의 점수를 획득 -> get_score()
3. 다음 주사위의 이동 방향 결정 -> next_dir()
'''

#주사위가 굴러갈 때 상태 표시
def roll_dice(d):
    global dice # 윗면, 북, 동, 남, 서, 아랫면

    if d == 0: # 동
        tmp = dice[2] # 동쪽 저장   
        dice[2] = dice[0] 
        dice[0] = dice[4] 
        dice[4] = dice[5] 
        dice[5] = tmp 

    elif d == 1: # 남
        tmp = dice[3]
        dice[3] = dice[0]
        dice[0] = dice[1]
        dice[1] = dice[5] 
        dice[5] = tmp 

    elif d == 2: # 서
        tmp = dice[4] # 서쪽 저장
        dice[4] = dice[0]
        dice[0] = dice[2]
        dice[2] = dice[5]
        dice[5] = tmp

    elif d == 3: #북
        tmp = dice[1] # 북쪽 저장
        dice[1] = dice[0] 
        dice[0] = dice[3] 
        dice[3] = dice[5] 
        dice[5] = tmp 

# 점수 획득을 위해 BFS 실행
def get_score(i, j):
    global dir

    cnt = 1
    value = board[i][j]
    visited = [[0 for _ in range(m)] for _ in range(n)]

    visited[i][j] = 1

    q = deque()
    q.append((i, j))

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

        for i in range(4):
            nx = x + dir[i][0]
            ny = y + dir[i][1]

            if in_range(nx, ny):
                if not visited[nx][ny] and board[nx][ny] == value: # 아직 미방문, 같은 정수를 가진 칸
                    visited[nx][ny] = 1
                    q.append((nx, ny))
                    cnt += 1

    return value * cnt

# 범위 내에서 동작하는가 : bool
def in_range(x, y):
    if 0<=x<n and 0<=y<m:
        return 1

    return 0

# 다음 방향 결정
def next_dir(x, y, d):
    global dice

    dice_value = dice[5] # 주사위 바닥의 정수
    board_value = board[x][y] # 보드의 정수

    if dice_value > board_value: # 이동방향 시계 회전
        d += 1
        if d > 3:
            d = 0

    elif dice_value < board_value:
        d -= 1
        if d < 0:
            d = 3

    nx = x + dir[d][0]
    ny = y + dir[d][1]

    if not in_range(nx, ny):
        return (d+2) % 4

    return d

n, m, k = map(int, input().rstrip('\n').split())
board = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]

#주사위 초기 상태 : 윗면, 북, 동, 남, 서, 아랫면
dice = [1, 2, 3, 5, 4, 6]

# 방향: 동, 남, 서, 북(시계 방향)
dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]

res = 0
x, y, d = 0, 0, 0

for _ in range(k):
    cx = x + dir[d][0]
    cy = y + dir[d][1]

    roll_dice(d)
    res += get_score(cx, cy)
    d = next_dir(cx, cy, d)
    x, y = cx, cy

print(res)

2021년 하반기 오전 1번 문제이다.
골드 3이지만 체감상 난이도는 무난했다. 시험장에서 마주쳤어도 어렵지 않게 풀어냈을 것 같다.

시간 재고 풀었는데 디버깅까지 한시간 살짝 넘게 걸려서, 바로 온풍기 안녕! 에 도전했다가 왕창 깨졌다,,
(한 세시간 걸렸네요 ㅠㅠ)

 

화이팅하자!!