#17825 주사위 윷놀이

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

17825번: 주사위 윷놀이

 

문제

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

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

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

 

입력

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

 

출력

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

 

풀이

 

각 보드의 연결관계를 다음과 같이 그래프로 표현하여 초기화

 

필요한 함수 및 변수

player[4]: 말 4개의 위치를 저장 (0에서 시작, 30 도착)

visit[35]: 도착한 위치에 말이 있으면 안됨 (중복 방지 )

move함수: 주사위에 쓰인 숫자만큼 이동

simul 함수: 재귀를 사용하여 가능한 모든 말들의 이동을 고려하여 이동, 함수 내에서 현재 턴에서 모든 말들의 이동 경우를 move함수를 실행하여 고려하는데 만약 말의 이동이 중복이 된다면 그 말은 이동시키지 않는다. 나머지는 다음 턴으로 넘긴다.

 

코드