[백준] 23299 주사위 굴리기 2 Python

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

23288번: 주사위 굴리기 2

그래프탐색이 가미된 시뮬레이션 문제이고, 알고리즘 순서는 다음과 같다.

1. 입력
2. 시뮬레이션 (k번)
2-1. 주사위 이동
2-2. 점수 획득: 그래프 탐색
2-3. 다음 이동방향 결정
3. 출력

주사위 이동을 할때 주사위의 위치를 변경하면서 주사위 면도 변경했다. 주사위의 첫 면이 1 2 3 4 5 6 이라 하고 top이 1 bottom이 6이라고 할때 동쪽으로 굴러가면 4 2 1 6 5 3 으로 변경한다. 모든 방향에 대해서 변경하기위해 dice라는 배열을 만들어놓고 방향에 맞게 값을 서로 변경했다.

점수 획득할땐 그래프 탐색을 사용했다. 나는 BFS를 사용했고 해당 주사위 칸과 점수가 같으면서 연결된 점을 찾고, 연결된 만큼 점수를 추가했다.

다음 이동 방향은 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸 (x, y)에 있는 정수 B를 비교해 이동 방향을 결정하면 된다. 비교에 따라 시계방향, 반시계 방향으로 바꿔주면 되므로 direction에 +1, -1을 더했다.

칸을 벗어나 반대 방향을 가는 경우가 생긴다. 이는 주사위 이동을 할 때 체크해서 해결 했다. 주사위 이동할때 반대 방향으로 가게 되면 그이후 주사위 방향을 바꿀때와 다음 이동 방향을 구할때도 영향이 가도록 만들었다.

 

# import sys; input = sys.stdin.readline
from collections import deque
d = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # r d l u, clockwise

def move(pos, direction):
    global N, M
    if 0 > direction or direction > 3:
        return False
    r, c = pos
    nr, nc = r + d[direction][0], c + d[direction][1]
    change_direction = False
    if 0 >= nr or nr > N or 0 >= nc or nc > M:
        ndir = (direction + 2) % 4
        nr, nc = r + d[ndir][0], c + d[ndir][1]
        change_direction = True

    pos[0], pos[1] = nr, nc
    return change_direction

def change_dice(dice, direction, move_opposite):
    if 0 > direction or direction > 3:
        return
    real_dir = (direction + move_opposite * 2) % 4
    if 0 == real_dir:
        # rolling east
        dice[1], dice[3], dice[4], dice[6] = \
            dice[4], dice[1], dice[6], dice[3]
    elif 1 == real_dir:
        # rolling south
        dice[1], dice[2], dice[5], dice[6] = \
            dice[2], dice[6], dice[1], dice[5]
    elif 2 == real_dir:
        # rolling west
        dice[1], dice[3], dice[4], dice[6] = \
            dice[3], dice[6], dice[1], dice[4]
    elif 3 == real_dir:
        # rolling north
        dice[1], dice[2], dice[5], dice[6] = \
            dice[5], dice[1], dice[6], dice[2]
    return

def get_score(pos):
    # graph traversal(BFS)
    global N, M, _map
    score = 0
    visit = [[0 for _ in range(M + 2)] for _ in range(N + 2)]
    q = deque()
    q.append(pos)
    while q:
        r, c = q.popleft()
        if visit[r][c]: continue
        visit[r][c] = 1
        score += _map[pos[0]][pos[1]]
        for dr, dc in d:
            nr, nc = r + dr, c + dc
            if 0 < nr <= N and 0 < nc <= M:
                if _map[nr][nc] == _map[pos[0]][pos[1]]:
                    q.append((nr, nc))

    return score


def get_next_direction(direction, move_opposite, A, B):
    next_direction = (direction + move_opposite * 2) % 4
    if A > B:
        next_direction += 1
    elif A < B:
        next_direction -= 1
    else:
        # no change
        pass
    return next_direction % 4

def main():
    global N, M, _map
    # 0 input
    N, M, K = map(int, input().split())
    _map = [[0 for _ in range(M + 2)]]      # make boundary
    for _ in range(N):
        tmp = [0]                           # make boundary
        tmp.extend(map(int, input().split()))  # real value
        tmp.append(0)                       # make boundary
        _map.append(tmp)
    _map.append([0 for _ in range(M + 2)])  # make boundary
    dice = list(range(7))                   # init dice array

    # 1 simulation
    answer = 0
    pos = [1, 1]    # initial position
    direction = 0   # initial direction is right
    for _ in range(K):
        move_opposite = move(pos, direction)
        change_dice(dice, direction, move_opposite)
        answer += get_score(pos)
        direction = get_next_direction(direction, move_opposite, dice[6], _map[pos[0]][pos[1]])

    # 2 output
    print(answer)


if __name__ == "__main__":
    main()

작년에 삼성 코딩테스트에서 직접 풀었던 문제여서 그런지 쉽게 풀었다.