[백준 17825] 주사위 윷놀이

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

17825번: 주사위 윷놀이

---

접근

4개의 말로 10개의 턴이 진행된다. 주사위에 나오는 숫자는 미리 알고있다. 그렇다면 매 턴마다 어떤 말을 이동할지 선택해야 한다. 이를 비트시프트를 활용하여 모든 경우의 수를 구하여 말을 선택한다.

0부터 1 << 20 까지 탐색을 진행하면 위와 같은 형태의 이진수가 나타날 것이다. 뒤에서 2개씩 짜른 후에 3과 AND 연산을 하면 어떤 말을 선택해야하는지 알 수 있다. 말을 선택했다면 해당 턴에 움직여야하는 칸만큼 이동하도록 한다.

 

말을 이동할 때는 어떻게해야 할지 고민이었다. 문제에서 주어진 맵을 2차원 리스트로 구현하였다. 시작과 도착 칸을 포함하여 총 33칸이 존재하며 각각의 행에서 첫 번째 열은 해당 칸의 점수, 두 번째부터는 1부터 5까지 진행했을 때 이동해야 하는 칸의 인덱스가 포함되도록 한다. 이제 해당 맵을 활용하여 구현해보자.

 

구현

- 10개의 턴에 대해 이동해야하는 칸의 수를 turn에 저장한다.

- 이후 1<<20까지 탐색하여 해당 수를 함수 game에 전달한다.

turn = list(map(int, input().split()))
answer = 0
for i in range(1<<20):
    game(i)

- horses는 말의 현재 위치를 담고있다.

- visited는 각각의 위치에 말이 있는지를 판단할 수 있다.

- 10번의 턴이 진행되면서 i번째 턴의 전진 수를 step에 저장한다.

- 이후 입력받은 N을 2개씩 오른쪽으로 시프트하여 말을 선택하도록 한다.

- 선택된 말은 horse이며 현재 horse의 위치를 cur_pos에 저장한다.

- 이후 horse의 다음 위치를 board를 통해 알아본다.

- 만약 다음위치에 다른 말이 있거나 도착점이 아닐 때 return한다.

- 그렇지 않을 때는 cur_pos 위치를 False로 하고 next_pos를 True로 하여 말을 이동시킨다.

- 이제 다음 위치의 첫 번째 인덱스의 수를 score에 더해준다.

- 10번의 턴이 종료되면 최댓값 비교를 진행한다.

def game(N):
    global answer
    horses = [0 for _ in range(4)]
    visited = [False for _ in range(33)]
    score = 0
    for i in range(10):
        step = turn[i]
        horse = (N >> (i * 2)) & 0x03
        cur_pos = horses[horse]
        next_pos = board[cur_pos][step]
        if visited[next_pos] and next_pos != 32:
            return
        visited[cur_pos] = False
        visited[next_pos] = True
        horses[horse] = next_pos
        score += board[next_pos][0]


    answer = max(answer, score)

---

전체 코드

import sys
input = sys.stdin.readline

board = [
    [0, 1, 2, 3, 4, 5],
    [2, 2, 3, 4, 5, 6],
    [4, 3, 4, 5, 6, 7],
    [6, 4, 5, 6, 7, 8],
    [8, 5, 6, 7, 8, 9],
    [10, 21, 22, 23, 29, 30],
    [12, 7, 8, 9, 10, 11],
    [14, 8, 9, 10, 11, 12],
    [16, 9, 10, 11, 12, 13],
    [18, 10, 11, 12, 13, 14],
    [20, 24, 25, 29, 30, 31],
    [22, 12, 13, 14, 15, 16],
    [24, 13, 14, 15, 16, 17],
    [26, 14, 15, 16, 17, 18],
    [28, 15, 16, 17, 18, 19],
    [30, 26, 27, 28, 29, 30],
    [32, 17, 18, 19, 20, 32],
    [34, 18, 19, 20, 32, 32],
    [36, 19, 20, 32, 32, 32],
    [38, 20, 32, 32, 32, 32],
    [40, 32, 32, 32, 32, 32],
    [13, 22, 23, 29, 30, 31],
    [16, 23, 29, 30, 31, 20],
    [19, 29, 30, 31, 20, 32],
    [22, 25, 29, 30, 31, 20],
    [24, 29, 30, 31, 20, 32],
    [28, 27, 28, 29, 30, 31],
    [27, 28, 29, 30, 31, 20],
    [26, 29, 30, 31, 20, 32],
    [25, 30, 31, 20, 32, 32],
    [30, 31, 20, 32, 32, 32],
    [35, 20, 32, 32, 32, 32],
    [0, 32, 32, 32, 32, 32]
]

def game(N):
    global answer
    horses = [0 for _ in range(4)]
    visited = [False for _ in range(33)]
    score = 0
    for i in range(10):
        step = turn[i]
        horse = (N >> (i * 2)) & 0x03
        cur_pos = horses[horse]
        next_pos = board[cur_pos][step]
        if visited[next_pos] and next_pos != 32:
            return
        visited[cur_pos] = False
        visited[next_pos] = True
        horses[horse] = next_pos
        score += board[next_pos][0]


    answer = max(answer, score)


turn = list(map(int, input().split()))
answer = 0
for i in range(1<<20):
    game(i)

print(answer)