[백준] 17825 주사위 윷놀이

---

이동할 수 있는 말에 대한 경우의 수를 백트래킹 알고리즘으로 구해 해결할 수 있다.

 

유의 해야 할 부분은 윷판에 지름길이 존재한다는 것이다. 나는 지름길을 처리하기 위해서 루트를 0 - 4로 나누었다.

route0에서 처리

route0에서 고려해야할 것은 5, 10, 15 번에서 출발할 경우 지름길을 통하는 것이다. 5는 1번루트, 10은 2번루트 마지막으로 15는 3번 루트로 변경한다. 그리고 이동 해야 할 거리는 주사위의 숫자 크기를 따른다.

 

그리고 route0에서 말이 이동할 때 19 번을 넘을 겅우 route4로 루트를 변경 해야 한다. 이떄 route0의 길이를 오프셋으로 하고 이동 해야할 위치에서 오프셋을 빼준 후 다시 route4의 길이 - 1을 더해 위치를 변경한다.

 

예를 들어 route0, 현재 위치 18에서 주사위가 2가 나온다면 새로운 위치는 18 + 5 = 20이 된다.

 

23은 route0의 길이(20) 보다 크기 때문에 route4로 변경해야 한다. 따라서 20 - 20 + 4 - 1 = 3 이 되어 route4의 마지막에 위치하여 40 점을 획득할 수 있다.

 

route1, 2, 3 에서 처리

세 루트에서는 이동 위치가 각 루트의 길이를 넘어갈 때 route4로 루트를 변경하는 작업만 수행하면 된다. 이때 각 루트의 길이를 오프셋으로 하여 이동할 위치에서 빼준다.

 

route4 에서 처리

 

이제 route0, 1, 2, 3에서 이동할 위치가 각 루트의 길이를 넘을 경우 route4로 변경 되었기 때문에 도착지로 이동하는 부분은 route4에서만 처리하면된다. 

 

말을 이동하되 이동 위치가  route4의 길이를 넘을 경우 도착지로 이동하면된다.

 

route 0 - 4에서 이동 위치가 각 루트의 길이를 넘지 않을 경우

이때는 정상적으로 각 루트 내 위치로 이동하면된다. 단 이동할 위치에 말이 존재할 경우 이동할 수 없기 때문에 각 말의 위치를 확인하고 만약 다른 말이 해당 위치에 존재 한다면 다른 말을 선택하여 처음부터 알고리즘을 수행할 수 있도록 한다.

 

Python

 

Java