[BOJ/백준] 23288 주사위 굴리기2 파이썬/Python3

[BOJ/백준] 23288 주사위 굴리기2 파이썬/Python3

주사위 굴리기 2 성공

 

 

 

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

23288번: 주사위 굴리기 2

 

1. 문제 풀이

---

1. 해당 문제는 기존에 출제되었던 주사위 문제의 업그레이드

2. 문제에 주어진 대로 구현하면 해결할 수 있는 문제 (주사위 인덱스를 변경하는 과정에서 실수가 잦을 수 있음)

3. bfs 탐색 알고리즘을 활용해서 주사위의 밑면의 수와 같은 수로 이루어진 칸이 몇 칸인지를 찾기 위해 활용

4. dice_move 함수를 활용해 주사위의 이동방향과 이동한 칸의 좌표를 갱신한다.

5. change_dice 함수를 활용해서 주사위 동, 서, 남, 북으로 굴러갈 경우를 경우를 분류해 주사위의 값을 변경

6. bfs 함수를 활용해 C 의 값을 구해준다.

7. 최종 점수 score에 현재 주사위가 놓인 그래프의 값 * C을 누적해서 더해준다.

8. 주사위의 밑면 값 dice[5]와 현재 그래프의 값 B를 비교해 90도 시계, 반시계 방향으로 d값을 갱신한다.

9. 최종 누적 합계를 출력해준다.

from collections import deque
from copy import deepcopy

# n 행 m 열 k 이동 횟수
n, m, k = map(int, input().split())
# 지도
graph = [list(map(int, input().split())) for _ in range(n)]
# 초기 주사위 윗면 1, 동쪽 3, 아랫면 6

# 초기 주사위 좌표
dice = [2, 4, 1, 3, 5, 6]
d = 0


def change_dice(dice, d):
    # 동쪽 이동
    if d == 0:
        # dice = [2, 6, 4, 1, 5, 3]
        dice[1], dice[2], dice[3], dice[5] = dice[5], dice[1], dice[2], dice[3]
    # 남쪽 이동
    elif d == 1:
        # dice = [6, 4, 2, 3, 1, 5]
        dice[0], dice[2], dice[4], dice[5] = dice[5], dice[0], dice[2], dice[4]
    # 서쪽 이동
    elif d == 2:
        # dice = [2, 1, 3, 6, 5, 4]
        dice[1], dice[2], dice[3], dice[5] = dice[2], dice[3], dice[5], dice[1]
    # 북쪽 이동
    elif d == 3:
        # dice = [1, 4, 5, 3, 6, 2]
        dice[0], dice[2], dice[4], dice[5] = dice[2], dice[4], dice[5], dice[0]

    return dice

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

x, y = 0, 0
d = 0
score = 0


# 주사위의 범위 체크
def check(a, b):
    if a < 0 or a > n - 1 or b < 0 or b > m - 1:
        return True
    return False


# 주사위의 이동
def dice_move(a, b, d) -> object:
    na, nb = a + vector[d][0], b + vector[d][1]
    # 1. 이동 방향에 칸이 없는 경우
    if check(na, nb):
        nd = (d + 2) % 4
        na, nb = a + vector[nd][0], b + vector[nd][1]
        return [na, nb, nd]

    # 2. 이동 방향에 칸이 있는 경우
    return [na, nb, d]


# 연속해서 이동할 수 있는 칸의 개수 조사
def bfs(a, b):
    cnt = 1
    visited = [[0]*m for _ in range(n)]
    q = deque()
    q.append([a, b])
    while q:
        x, y = q.popleft()
        visited[x][y] = 1
        for i in range(4):
            nx, ny = x + vector[i][0], y + vector[i][1]
            if check(nx, ny):
                continue

            if graph[x][y] == graph[nx][ny] and not visited[nx][ny]:
                visited[nx][ny] = 1
                q.append([nx, ny])
                cnt += 1
    return cnt


for _ in range(k):
    # 1. 주사위의 이동
    x, y, d = dice_move(x, y, d)
    dice = change_dice(dice, d)
    # 2. 주사위가 도착한 칸에 대한 점수 계산
    C = bfs(x, y)
    score += graph[x][y] * C
    # 3. 주사위의 이동 방향 결정
    A, B = dice[5], graph[x][y]
    # 이동방향 90도 시계방향 회전
    if A > B:
        d = (d + 1) % 4
    # 이동방향 90도 반시계방향 회전
    elif A < B:
        d = (d - 1)
        if d == -1:
            d = 3
    # 이동방향 변화 없음
    elif A == B:
        pass

# 점수의 합 출력
print(score)