파이썬으로 풀어보는 백준 17825번: 주사위 윷놀이 (삼성 SW 역량 테스트 기출 문제)

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

17825번: 주사위 윷놀이

 

 

내 풀이:

def game(idx, horses, score):
    global ans
    check_set = set()
    start_end = 0
    for i in range(4):
        location = table[horses[i][0]][horses[i][1]]
        if location == 0 or location == 1000:
            start_end += 1
        else:
            check_set.add(location)
    if len(check_set) + start_end < 4:
        return
 
    if idx == 10:
        ans = max(ans, score%1000)
        return
 
    for i in range(4):
        if i > 0 and horses[i-1][1] == 0:
            continue
        if table[horses[i][0]][horses[i][1]] == 1000:
            continue
        prev = (horses[i][0], horses[i][1])
        horses[i][1] += dice[idx]
        if table[horses[i][0]][horses[i][1]] == 10:
            horses[i][0] = 1
        elif table[horses[i][0]][horses[i][1]] == 20:
            horses[i][0] = 2
        elif table[horses[i][0]][horses[i][1]] == 30:
            horses[i][0] = 3
        game(idx+1, horses, score + table[horses[i][0]][horses[i][1]])
        horses[i][0], horses[i][1] = prev
 
 
dice = list(map(int,input().split()))
table = []
table.append([i for i in range(0, 41, 2)] + [1000] * 5)
table.append([0] * 5 + [10, 13, 1016, 19, 25, 1030, 35, 40] + [1000] * 5)
table.append([0] * 10 + [20, 1022, 1024, 25, 1030, 35, 40] + [1000] * 5)
table.append([0] * 15 + [30, 1028, 27, 1026, 25, 1030, 35, 40] + [1000] * 5)
 
horses = [[0, 0] for _ in range(4)]
ans = 0
game(0, horses, 0)
print(ans)

Python3, 132ms

시뮬레이션 구현 문제 중 체감상 가장 어려웠던 문제이다. 이유는 지름길을 탔을 때와 타지 않은 경로상에 같은 수가 존재하여 구분하기 매우 어렵다. 이 문제에서는 같은 수가 3번 이상 등장하진 않기 때문에 중복되는 수에 1000을 더하여 처리해주었다. 이후 답을 출력할 때 1000으로 나눈 나머지를 출력하면 문제를 다소 쉽게 해결할 수 있다.