Easy is Perfect

[백준] 17825번 주사위 윷놀이 _ 문제 풀이

  • melonicedlatte
  • Mar 28, 2021


1. 문제

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

2. 풀이

삼성 SW 역량테스트 문제입니다. 풀이 순서는 아래와 같습니다.

image

  1. 위와 같이 원들에 대하여 index를 지정해놓고, 배열을 이용하여 [점수, 다음 index]를 기록해놓습니다.
  2. dfs를 이용하여 모든 경우의 수를 확인합니다. 4개의 말에 대하여 10번의 turn 에 대하여 모두 확인해봐도 4^10 이기 때문에 그렇게 큰 숫자가 아닙니다.
START, END = 0, 32
horse = [0,0,0,0]
dice_list = list(map(int, input().split()))
answer = 0
# [score, next]
DIC=[[0,1],[2,2],[4,3],[6,4],[8,5],         [10,6],[12,7],[14,8],[16,9],[18,10],
 [20,11],[22,12],[24,13],[26,14],[28,15],   [30,16],[32,17],[34,18],[36,19],[38,20],
 [40,32],[13,22],[16,23],[19,24],[25,30],   [22,26],[24,24],[28,28],[27,29],[26,24],
 [30,31],[35,20],[0,32]]
BLUE_DIC={}; BLUE_DIC[5]=[10, 21] ; BLUE_DIC[10]=[20, 25] ;  BLUE_DIC[15]=[30, 27]

def dfs(turn, score):
    global answer
    answer = max(answer, score)
    if turn == 10:
        return

    for i in range(4):
        # 주사위 만큼 이동
        before_idx = horse[i]
        # 이전께 Blue 갈 수 있으면 Blue로 감
        next_idx = BLUE_DIC[before_idx][1] if before_idx in BLUE_DIC else before_idx
        cycle = dice_list[turn] - 1 if before_idx in BLUE_DIC else dice_list[turn]
        for _ in range(cycle):
            next_idx = DIC[next_idx][1]

        # 전부 다 이동한 후 그 위치에 다른 얘들이 있으면
        if next_idx != 32 and horse.count(next_idx) >= 1:
            continue
        horse[i] = next_idx
        dfs(turn+1, score+DIC[next_idx][0])
        horse[i] = before_idx

dfs(0,0)
print(answer)



Search