[백준] 23288. 주사위 굴리기2/Python - Gold3

❓문제

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

성능 요약

메모리: 114372 KB, 시간: 184 ms

분류

구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색

 

문제 설명

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있는 칸의 좌표는 (N, M)이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 각 면에는 1보다 크거나 같고, 6보다 작거나 같은 정수가 하나씩 있다. 주사위 한 면의 크기와 지도 한 칸의 크기는 같고, 주사위의 전개도는 아래와 같다.

  2
4 1 3
  5
  6

주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (1, 1) 이다. 지도의 각 칸에도 정수가 하나씩 있다. 가장 처음에 주사위의 이동 방향은 동쪽이다. 주사위의 이동 한 번은 다음과 같은 방식으로 이루어진다.

1. 주사위가 이동 방향으로 한 칸 굴러간다. 만약, 이동 방향에 칸이 없다면, 이동 방향을 반대로 한 다음 한 칸 굴러간다.
2. 주사위가 도착한 칸 (x, y)에 대한 점수를 획득한다.
3. 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸 (x, y)에 있는 정수 B를 비교해 이동 방향을 결정한다.
   • A > B인 경우 이동 방향을 90도 시계 방향으로 회전시킨다.
   • A < B인 경우 이동 방향을 90도 반시계 방향으로 회전시킨다.
   • A = B인 경우 이동 방향에 변화는 없다.

칸 (x, y)에 대한 점수는 다음과 같이 구할 수 있다. (x, y)에 있는 정수를 B라고 했을때, (x, y)에서 동서남북 방향으로 연속해서 이동할 수 있는 칸의 수 C를 모두 구한다. 이때 이동할 수 있는 칸에는 모두 정수 B가 있어야 한다. 여기서 점수는 B와 C를 곱한 값이다.

보드의 크기와 각 칸에 있는 정수, 주사위의 이동 횟수 K가 주어졌을때, 각 이동에서 획득하는 점수의 합을 구해보자.

이 문제의 예제 1부터 7은 같은 지도에서 이동하는 횟수만 증가시키는 방식으로 구성되어 있다. 예제 8은 같은 지도에서 이동하는 횟수를 매우 크게 만들었다.

✍🏻풀이

먼저 동서남북으로 주사위를 굴렸을 때 주사위가 어떻게 바뀌는지 알아야 한다. 주사위를 리스트로 [2, 1, 4, 3, 5, 6]으로 표현해보았다. 주사위 리스트 명칭은 dice로 하겠다.

그러면 이 주사위를 동으로 움직였을 때 주사위는 [2, 4, 6, 1, 5, 3]으로 바뀐다는 것을 알 수 있다. 여기서 바뀐 위치만 본다면 dice[2] ➡️ dice[1], dice[5] ➡️ dice[2], dice[1] ➡️ dice[3], dice[3] ➡️ dice[5]가 된다. 마찬가지로 남, 서, 북도 확인함으로써 주사위가 굴렀을 때 어떻게 바뀌는지 알 수 있다.

그럼 이제 주사위를 굴리면서 주사위 아랫면과 해당 칸의 수를 비교하면서 탐색하면 된다. 여기서 탐색은 너비 탐색으로 이 문제는 BFS를 이용해 풀면 된다. 그러므로 큐에 현재 위치와 방향을 같이 기록하면서 탐색하면 된다. 그리고 탐색하면서 주사위 아랫면의 수와 현재 위치의 수를 비교해 주사위를 시계, 반시계로 90도 돌리면 된다.

이때 칸의 수가 주사위 아랫면 보다 작으면 시계방향으로 90도를 돌려 동 ➡️ 남 ➡️ 서 ➡️ 북이 되고, 칸의 수가 주사위 아랫면보다 크면 반시계 방향으로 90도를 돌려 동 ➡️ 북 ➡️ 서 ➡️ 남이 된다. 동을 0, 남을 1, 서를 2, 북을 3으로 주고 시계 방향일 때는 (i+1)%4로 방향을 바꾸고, 반시계 방향일 때는 (i-1)%4로 방향을 바꾸면 된다. 그런데 바꾼 방향으로 더 이상 갈 수 없다면 반대 방향으로 돌아서 가야 한다. 그러므로 이 때는 (i+2)%4를 하면 180도로 돌 수 있다.

그리고 주사위를 움직였으면 점수를 계산해야 한다. 점수를 계산할 때는 지나갔던 칸을 다시 지나가면 안 되므로 방문을 표시해야 한다. 점수는 해당 칸에서 동서남북으로 움직일 수 있으면서 같은 숫자인 칸을 연속해서 몇 번 갈 수 있는지 탐색한 후 갈 수 있는 칸 개수와 현재 칸의 수를 곱하면 된다. 

위 내용을 코드로 풀이하면 아래와 같이 풀 수 있다.

💻코드

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

N, M, K = map(int, input().split()) # N 세로 크기, M 가로 크기, 이동하는 횟수 K
board = [list(map(int, input().split())) for _ in range(N)]
# 동 남 서 북
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

# 1 -> 윗면, 6 -> 아랫면
dice = [2, 1, 4, 3, 5, 6]
q = deque([(0, 0, 0)]) # y, x, d
k = 0
result = 0

def score(y, x):
    visited = [[False for _ in range(M)] for _ in range(N)]
    q = deque([(y, x)])
    count = 1
    visited[y][x] = True
    while  q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < N and 0 <= nx < M and not visited[ny][nx] and board[ny][nx] == board[y][x]:
                    visited[ny][nx] = True
                    q.append((ny, nx))
                    count += 1

    return count

def rotate_dice(d):
    if d == 0:
        dice[1], dice[2], dice[3], dice[5] = dice[2], dice[5], dice[1], dice[3]
    elif d == 1:
        dice[0], dice[1], dice[4], dice[5] = dice[5], dice[0], dice[1], dice[4]
    elif d == 2:
        dice[1], dice[2], dice[3], dice[5] = dice[3], dice[1], dice[5], dice[2]
    elif d == 3:
        dice[0], dice[1], dice[4], dice[5] = dice[1], dice[4], dice[5], dice[0]

while q and k < K:
    y, x, d = q.popleft()
    if y + dy[d] < 0 or y+dy[d] >= N or x + dx[d] < 0 or x + dx[d] >= M:
        d = (d + 2) % 4
    y += dy[d]
    x += dx[d]
    rotate_dice(d)
    if board[y][x] < dice[5]:
        d = (d+1) % 4
    elif board[y][x] > dice[5]:
        d = (d-1) % 4

    result += board[y][x] * score(y, x)
    q.append((y, x, d))

    k += 1

print(result)

📍후기

문제가 쉬운 건지 아니면 내가 BFS는 이제 숙달이 된 것인지...