[백준] 17825 - 주사위 웇놀이 (파이썬, Python)

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

17825번: 주사위 윷놀이

 

이 문제는 백트래킹, 구현 문제입니다.

주사위를 굴려서 나올 10개의 숫자를 미리 알려주고, 말을 이동시켜 얻을 수 있는 최대 점수를 구하는 것이 이 문제의 목표입니다.

 

이 문제는 이름에도 윷놀이가 있듯이 윷놀이처럼 지름길이 있습니다.

지름길은 10, 20, 30 칸에서 출발을 해야 갈 수 있으며 이동 중간에 해당 칸들을 지나는 경우는 지름길로 갈 수 없습니다.

 

말은 해당 회차에서 주사위를 굴려 나온 수 만큼 진행방향으로 이동시킵니다.

다만, 이동시킬 칸에 이미 말이 존재하면 해당 말은 이동시킬 수 없습니다.(도착 칸은 제외입니다.)

 

이 문제는 구현 문제인 만큼 문제에 주어진 조건대로 실수 없이 구현을 하면 됩니다.

 

접근 방식

1. 현재 재귀가 10 턴을 모두 수행했으면 현재까지 점수가 최댓값인지 판단 후 재귀 종료

2. 현재 턴의 주사위 수를 이용해서 현재 판에 있는 말 들의 다음 위치를 계산, 만약 다음 위치에 말이 존재하지 않는다면 말을 해당 위치로 이동시킨 후 새로운 재귀 생성

3. 만약 현재 재귀에서 아직 시작 칸에 있는 말이 있고, 현재 턴의 주사위 수를 이용해서 다음 위치를 확인한 후 다음 위치에 말이 존재하지 않는다면 말을 해당 위치로 이동시킨 후 새로운 재귀 생성

4. 1~3을 모든 재귀가 종료될 때까지 반복

전체 코드

제출 언어: PyPy3

시간: 544ms

 

from copy import deepcopy
import sys

def check(next_pos, cur_pos_unit, next_is_boundary):
    is_can_moved = True

    for pos, is_boundary in cur_pos_unit:
        if pos > 40:
            continue

        elif next_pos == pos and next_is_boundary == is_boundary:
            is_can_moved = False
            break

    return is_can_moved

def move(cmd_idx, unit_cnt, prev_pos_unit, cur_score):
    global cmds, pos_10, pos_20, pos_30, pos_25, answer

    if cmd_idx == 10:
        answer = max(answer, cur_score)
        return

    cur_cmd = cmds[cmd_idx]

    for idx in range(len(prev_pos_unit)):
        cur_pos_unit = deepcopy(prev_pos_unit)
        pos, is_boundary = prev_pos_unit[idx]
        next_pos = pos
        next_score = cur_score

        if pos > 40:
            continue

        elif is_boundary:
            if pos == 10:
                next_pos = pos_10[cur_cmd-1]
                is_boundary = False

            elif pos == 20:
                next_pos = pos_20[cur_cmd-1]
                is_boundary = False

            elif pos == 30:
                next_pos = pos_30[cur_cmd-1]
                is_boundary = False
            
            else:
                next_pos = pos + cur_cmd * 2

        else:
            if pos in pos_10:
                pos_idx = pos_10.index(pos)

                if pos_idx + cur_cmd > 6:
                    next_pos = 41
                else:
                    next_pos = pos_10[pos_idx+cur_cmd]
                
            elif pos in pos_20:
                pos_idx = pos_20.index(pos)

                if pos_idx + cur_cmd > 5:
                    next_pos = 41
                else:
                    next_pos = pos_20[pos_idx+cur_cmd]
                
            elif pos in pos_30:
                pos_idx = pos_30.index(pos)

                if pos_idx + cur_cmd > 6:
                    next_pos = 41
                else:
                    next_pos = pos_30[pos_idx+cur_cmd]
        
        if next_pos == 40:
            is_boundary = True
            
        is_can_moved = check(next_pos, cur_pos_unit, is_boundary)
        
        if is_can_moved:
            if next_pos <= 40:
                next_score += next_pos
            cur_pos_unit[idx] = [next_pos, is_boundary]

            move(cmd_idx+1, unit_cnt, cur_pos_unit, next_score)

    if unit_cnt > 0:
        cur_pos_unit = deepcopy(prev_pos_unit)
        
        if cur_cmd * 2 not in [ pos for pos, _ in cur_pos_unit ]:
            cur_pos_unit.append([cur_cmd * 2, True])
            next_score = cur_score + cur_cmd * 2
            move(cmd_idx+1, unit_cnt-1, cur_pos_unit, next_score)  
        
if __name__ == "__main__":
    cmds = list(map(int, sys.stdin.readline().strip().split()))

    pos_10 = [13, 16, 19, 25, 30, 35, 40]
    pos_20 = [22, 24, 25, 30, 35, 40]
    pos_30 = [28, 27, 26, 25, 30, 35, 40]

    cmd_idx = 0
    answer = float('-inf')
    unit_cnt = 4
    pos_unit = []

    move(cmd_idx, unit_cnt, pos_unit, 0)

    print(answer)

---

읽어 주셔서 감사합니다 :)

틀린 부분이 있다면 댓글로 편히 알려주세요😊