[파이썬/Python] 백준 14499번: 주사위 굴리기

숨·2025년 1월 14일

알고리즘 문제 풀이

목록 보기

99/105

📌 문제 : 백준 14499번

📌 문제 탐색하기

N : 지도의 세로 크기 ( $1 ≤ N ≤ 20$ )
M : 지도의 가로 크기 ( $1 ≤ M ≤ 20$ )
x, y : 주사위 놓은 좌표 ( $0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1$ )
K : 명령의 개수

문제 풀이

크기가 N×M인 지도의 0이 쓰여져 칸에 주사위가 놓여져 있을 때, 명령에 따라 주사위가 이동할 때마다 상단에 쓰여 있는 값을 구해 출력하는 문제이다.

움직이기 전 처음 주사위의 모든 면엔 0이 적혀있다.
따라서 주사위의 각 면의 값을 이용하기 위해 조건에 따라 초기값 0으로 된 리스트를 만들어준다.

굴리는 방향에 따른 주사위 면 위치 변화

굴릴 때마다 주사위 면의 위치가 어떻게 바뀌는지에 대한 로직은 다음과 같다.
방향 변화
- 동 : [1,2,3,4,5,6] → [4,2,1,6,5,3]
- 서 : [1,2,3,4,5,6] → [3,2,6,1,5,4]
- 남 : [1,2,3,4,5,6] → [2,6,3,4,1,5]
- 북 : [1,2,3,4,5,6] → [5,1,3,4,6,2]
주사위의 각 면을 인덱스로 접근해서 굴릴 때마다 변경되는 각 면의 값을 찾아준다.
→ 이를 구현한 함수로 따로 만들어 이동할 때마다 호출해준다.

주사위의 이동

N×M의 범위를 벗어나지 않도록 명령에 따라 지도 위를 이동해야 한다.
- 가능한 이동 방향 = 4가지 (동서남북)
- 지도 밖으로 이동하려고 하면 명령 무시!
- 거쳤던 곳 다시 못간다는 조건 ❌ = 방문 기록 필요 ❌
이동하면 지도에 쓰여진 수에 따라 주사위의 숫자가 달라진다.
- 0 ⭕️ = 주사위 바닥면에 쓰여 있는 수 → 칸에 복사
- 0 ❌ = 칸에 쓰여 있는 수 → 주사위 바닥면에 복사 & 칸의 수 0

→ 명령 저장한 리스트에 하나씩 접근해서 범위 내 이동하도록 구현한다.

가능한 시간복잡도

지도 입력 → $O(N * M)$
명령을 하나씩 수행하면서 움직임 → $O(K)$

최종 시간복잡도
$O(K + N * M)$ 로,최악의 경우 $O(10^3 + 20^2)$ 이 되어 제한 시간 2초 내에 연산이 가능하다.

알고리즘 선택

for문으로 명령 수행하면서 지도 이동

📌 코드 설계하기

주사위 면 변화 함수 정의
N, M, x, y, K 입력
지도에 쓰여 있는 수 입력
이동 명령 입력
각 면의 값 초기화
이동 방향 정의
명령 수행
7-1. 주사위 면 변화
7-2. 주사위 숫자 변화
7-3. 결과 출력

📌 시도 회차 수정 사항

1회차

자꾸 틀린 출력이 나왔다.
알고보니 면을 바꿔주는 함수에서 남쪽일 경우의 변화하는 순서를 잘못 작성했기 때문이었다.

2회차

map_info의 x 인덱스, y 인덱스 순서를 반대로 썼다. x와 y의 좌표의 범위까지 다르게 적용하는 바람에 발생한 일이었다.

📌 정답 코드

import sys

input = sys.stdin.readline


# 주사위 면 변화 함수
def move_dice(order):
    if order == 1:  # 동쪽
        dice[0], dice[1], dice[2], dice[3], dice[4], dice[5] = dice[3], dice[1], dice[0], dice[5], dice[4], dice[2]
    elif order == 2:    # 서쪽
        dice[0], dice[1], dice[2], dice[3], dice[4], dice[5] = dice[2], dice[1], dice[5], dice[0], dice[4], dice[3]
    elif order == 3:    # 북쪽
        dice[0], dice[1], dice[2], dice[3], dice[4], dice[5] = dice[4], dice[0], dice[2], dice[3], dice[5], dice[1]
    else:   # 남쪽
        dice[0], dice[1], dice[2], dice[3], dice[4], dice[5] = dice[1], dice[5], dice[2], dice[3], dice[0], dice[4]


# N, M, x, y, K 입력
N, M, x, y, K = map(int, input().split())

# 지도에 쓰여 있는 수 입력
map_info = [list(map(int, input().split())) for _ in range(N)]

# 이동 명령 입력
orders = list(map(int, input().split()))

# 각 면의 값 초기화
dice = [0, 0, 0, 0, 0, 0]

# 이동 방향
moves = [(0, 1), (0, -1), (-1, 0), (1, 0)]

# 명령 수행
for order in orders:
    # 이동
    nx = x + moves[order - 1][0]
    ny = y + moves[order - 1][1]
    # 범위 내 이동
    if 0 <= nx < N and 0 <= ny < M:
        x, y = nx, ny
        # 주사위 면 변화
        move_dice(order)

        # 주사위 숫자 변화
        if map_info[x][y] == 0:
            map_info[x][y] = dice[5]
        else:
            dice[5] = map_info[x][y]
            map_info[x][y] = 0

        # 결과 출력
        print(dice[0])