[python] BOJ 백준 17825: 주사위 윷놀이

1. 문제  

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

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

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

2. 입력   

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

3. 출력   

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

4. 해결방법   

이 문제는 구현, DFS 문제이다. 보드판에 있는 점수를 인덱스에 맞게 b배열에 저장해주고, 파란색방향의 루트는 route 배열에 따로 저장해주었다. 그 다음 깊이 우선 탐색을 하면서 체스가 움직일 수 있는 모든경우의 수를 탐색하다가 10번의 주사위에 대해 다 움직였다면 그때 최대값을 업데이트해주면된다. 깊이 우선탐색을 하다가 다른말과 겹치게 되거나 이미 체스가 도착했다면 백트래킹하여 다음 체스를 움직여주면된다. 누적값은 계속해서 더해줘야하기 때문에 매개변수로 설정해주어야한다. 체스의 현재위치도 계속해서 변하기 때문에 매개변수로 설정해주고, 백트래킹할때 원래의 값으로 바꾸어주어야한다.  

1) dfs 함수: 체스 4개를 돌면서 도착한 칸이 아닐 경우에 현재 체스값에 따라 주사위를 움직였을때 다음위치를 계산해주면된다. 만약에 10점에 해당하는 파란방향이라면 10,13,16,19에 해당하는 방향을 route의 첫번째 배열에 저장해주었기 때문에 그 루트를 따라가면되고, 나머지 20과 30에 해당하는 파란방향도 똑같이 해주면된다. 다만 이때 인덱스 범위를 초과하는것에 대해서는 도착했다는 뜻이므로, 이때는 예외처리를 해주어야한다. 빨간방향도 마찬가지로 범위가 넘어가면 도착한것으로 판단, 범위가 넘어가지 않으면 그냥 더해주면된다. 

 

5) 구현코드   

dice=list(map(int,input().split())) #10개 주사위 수 
b=[0]*33  #점수표 
#파란색방향에 대한 루트 
routes=[[5,22,23,24,30,31,32,20,21],[10,25,26,30,31,32,20,21],[15,27,28,29,30,31,32,20,21]]
for i in range(21):
  b[i]=i*2
b[22],b[23],b[24]=13,16,19
b[25],b[26]=22,24
b[27],b[28],b[29],b[30],b[31],b[32]=28,27,26,25,30,35

chess=[0,0,0,0] #체스 4개의 현재위치 
answer=0 #최대값 


def dfs(i, chess,sum_num):
  global answer 
  if i==10: #10번 다돌면 최대값업데이트 
    answer=max(answer,sum_num)
    return 
  #체스 4개 돌면서 
  for c in range(4):
    temp=chess[c] #체스 현재값 
    if temp==21: #도착했으면 
      continue  #못고름 
    #파란색 첫번째 루트 
    if temp==5 or 22<=temp<=24:
      index=routes[0].index(temp)
      if dice[i]+index<=8: 
        next=routes[0][dice[i]+index]
      else: #범위 넘어가면 도착 
        next=21
    #파란색 두번째 루트 
    elif temp==10 or temp==25 or temp==26:
      index=routes[1].index(temp)
      if dice[i]+index<=7:
        next=routes[1][dice[i]+index]
      else: #범위넘어가면도착 
        next=21
    #파란색 세번째 루트 
    elif temp==15 or 27<=temp<=32:
      index=routes[2].index(temp)
      if dice[i]+index<=8:
        next=routes[2][dice[i]+index]
      else: #범위넘어가면도착 
        next=21
    #빨간색루트 
    else:
      if temp+dice[i]<=21:
        next=temp+dice[i]
      else: #범위넘어가면 도착 
        next=21
    #다른말과 안겹치면 
    if next in chess and next!=21:
      continue
    chess[c]=next #현재값 업데이트 
    dfs(i+1,chess,sum_num+b[next]) #DFS탐색 
    chess[c]=temp #백트래킹 

dfs(0,chess,0)
print(answer)

 

⭐️난이도:  골드 2 ⭐️

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

17825번: 주사위 윷놀이