(삼성기출) 백준 17825번 - 주사위 윷놀이 /Wanna Be 컴잘알

문제출처 : https://www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

-문제-

 

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

• 처음에는 시작 칸에 말 4개가 있다.
• 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
• 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

 

입력

 

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

 

출력

 

얻을 수 있는 점수의 최댓값을 출력한다.

 

-설명-

 

4개의 말에 순서를 부여하고 DFS로 완전탐색을 한다.

 

1. 윷놀이 판을 map 리스트에 만들어놓는다.

   map의 row=0일 때, 빨간길로만 간다.

   map의 row=1일 때, 10에서 꺾어서 간다.

   map의 row=2일 때, 15에서 꺾어서 간다.

   map의 row=3일 때, 20에서 꺾어서 간다.

   map의 row=4일 때, 25에서 꺾어서 간다.

 

2. moving함수 설명

  map의 row = 0 일때, len(map[0])이 col+1 과 같으면 도착점이므로 움직이지않는다.

  map의 row = 4 일때, len(map[4])이 col+1 과 같으면 row=0, col=19로 변환(즉, 윷놀이 판 상에서 40으로 이동)

  map의 row가 1 or 2 or 3 일때, len(map[1or2or3])이 col+1과 같으면 row=4, col = -1로 변환 (즉, 윷놀이 판상에서 25)

 

3. 방찍는 위치에 있는 경우에는

  row를 1,2,3에 맞춰서 이동시켜놓는다.

 

-코드-

import sys
input = sys.stdin.readline

maxValue = 0

def moving(i,move,check,map, horse, cnt):
    moveDistance = move[cnt]
    curRow = horse[i][0]
    curCol = horse[i][1]

    row = horse[i][0]
    col = horse[i][1]
    for i in range(0,moveDistance):
        if len(map[row]) == col+1:
            if row == 0:
                break
            elif row == 4:
                row = 0
                col = 19
            elif row == 1 or row == 2 or row ==3:
                row = 4
                col = -1
        col += 1
    
    if row ==0 and col == 5:
        row = 1
        col = 0
    elif row == 0 and col ==10:
        row = 2
        col = 0
    elif row == 0 and col == 15:
        row = 3
        col = 0
    
    if (row==0 and col==21) or check[row][col] == False:
        return [[True],[curRow,curCol],[row,col]]
    
    return [[False]]



def dfs(number, horse, map, move, check, sum, cnt, end):
    if cnt == end:
        global maxValue
        maxValue = max(maxValue,sum)
        return

    for i in range (4):
        if (horse[i][0] == 0 and horse[i][1] == 21):
            continue
        result = moving(i, move, check, map, horse, cnt)
        if result[0][0] == True:
            curRow = result[1][0]
            curCol = result[1][1]
            nextRow = result[2][0]
            nextCol = result[2][1]
            
            # 체크처리해줘야한다.
            check[curRow][curCol] = False
            check[nextRow][nextCol] = True
            horse[i][0] = nextRow
            horse[i][1] = nextCol
            dfs(i, horse, map, move, check, sum + map[horse[i][0]][horse[i][1]], cnt+1, len(move))# 0번째 말, 전체 말 위치, check
            check[curRow][curCol] = True
            check[nextRow][nextCol] = False
            horse[i][0] = curRow
            horse[i][1] = curCol


if __name__ == '__main__':
    move = list(map(int,input().split()))
    map = [
        [0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,0],
        [10,13,16,19], # map[0][5] 일때
        [20,22,24], # map[0][10] 일때
        [30,28,27,26], # map[0][15] 일때
        [25,30,35] # map[1][3] or map[2][2] or map [3][3] 보다 클 때
    ]

    check = [[False for _ in range(len(map[0]))] for _ in range(len(map[0]))]
    horse = [[0,0] for _ in range(4)]
    sum = 0
    cnt = 0
    dfs(0, horse, map, move, check, sum, cnt, len(move))
    print(maxValue)