[BOJ] 17825. 주사위 윷놀이 (🥇, 구현, 시뮬레이션)

🔗

풀이

일단 이동해야 하니까 그래프처럼 연결했다. 규칙성이 없어서 노가다로 연결해야 했다. 20번까지는 반복문 돌리고 나머진 진짜 다 씀. 0열에는 다음 이동해야 할 위치를, 1열에는 현재 칸에서 얻을 수 있는 점수를 기록함

""" 
* board
    - [다음으로 이동할 칸의 번호, 현재 칸에서 획득할 수 있는 점수]
"""
board = [[0, 0] for _ in range(33)]
for i in range(20):
    board[i] = [i+1, i*2]
board[21], board[22], board[23] = [22, 13], [23, 16], [29, 19]
board[24], board[25] = [25, 22], [29, 24]
board[26], board[27], board[28] = [27, 28], [28, 27], [29, 26]
board[29], board[30], board[31] = [30, 25], [31, 30], [20, 35]
board[20], board[32] = [32, 40], [0, 0]

이제 예외사항 몇 가지를 정리했다.

위치는 위의 그래프 그림에서 검은 펜으로 쓰여진 숫자를 의미한다.

1. 5, 10, 15 위치에서 시작되는 경우 파란색 방향을 따라야 한다.
2. 말을 선택할 수 있는 기준은 2가지이다
   • 도착하는 칸에 다른 말이 없는 경우
   • 도착 지점에 있는 말이 아닌 경우
3. 도착지에 도착했다면 주사위의 숫자가 남았더라도 종료한다
4. 구할 수 있는 최대값을 구해라

모든 경우의 수를 구하고 그 중 최대값을 구해야 한다. 백트래킹을 적절히 사용하지 않으면 시간이 오래걸릴 수 있다. 최대로 얻을 수 있는 점수는 40점이므로 앞으로 남은 칸의 개수x40을 해도 현재 구해진 최대값보다 커질 수 없다면 되돌아간다(백트래킹).

주사위의 값을 처음부터 끝까지 보면서 모든 말을 택하는 경우를 다 따져보게 된다. 이때 말을 도착지에 있으면 안 된다. 도착지에 있는 말들을 거른 후에는 이동을 마친 위치에 다른 말이 있는지를 확인한다. 둘 다 통과했다면 도착지 위치의 점수를 더하고 다음 주사위 값으로 넘어간다. 이때 지나치는 모든 칸의 점수를 다 더하는 걸로 했다가 2시간 삽질했다^^.

x는 주사위 칸의 숫자로 1씩 빼면서 반복문을 돌리면 0이 되었을 때 도착해야 하는 지점에 도달하게 된다. 이때 도착지에 다른 말이 있는지 확인한다. x가 시작지점일 때는 시작 위치가 5, 10, 15인지 확인하과 파란 방향을 따를 수 있도록 한다. 기본적으로 그래프는 빨간 방향을 따르고 있으므로 강제로 변경해야 한다. 도착지에 도착한 말은 여러개 있을 수 있다.

# 64ms

""" 
* board
    - [다음으로 이동할 칸의 번호, 현재 칸에서 획득할 수 있는 점수]
"""
board = [[0, 0] for _ in range(33)]
for i in range(20):
    board[i] = [i+1, i*2]
board[21], board[22], board[23] = [22, 13], [23, 16], [29, 19]
board[24], board[25] = [25, 22], [29, 24]
board[26], board[27], board[28] = [27, 28], [28, 27], [29, 26]
board[29], board[30], board[31] = [30, 25], [31, 30], [20, 35]
board[20], board[32] = [32, 40], [0, 0]

DICE = list(map(int, input().split()))
horse = [0]*4 # 말의 현재 위치
"""
* 전체 경우의 수 모두 구하기
    - i : 주사위 번호
    - j : 말의 번호
"""
def dfs(i, score):
    global ans 

    if score + 40*(10-i) <= ans:
        return 
    
    if i == 10:
        if ans < score:
            ans = max(ans, score)
        return
    
    for j in range(4):
        start = next = horse[j]
        if start == 32: # 이미 도착한 경우 제외
            continue
        x = DICE[i]

        while x:
            if x == DICE[i]:
                if start == 5:
                    next = 21
                elif start == 10:
                    next = 24
                elif start == 15:
                    next = 26
                else:
                    next = board[next][0]
            else:
                next = board[next][0]
            if next == 32:
                x = 0
                continue
            x -= 1

        if next != 32 and next in horse: # 도착지가 아닌데 다른 말이 도착지점에 이미 있음
            continue

        horse[j] = next
        dfs(i+1, score+board[next][1])
        horse[j] = start

ans = 0
dfs(0, 0)
print(ans)