[ 백준 17825 ] 주사위 윷놀이 (C++)

백준의 주사위 윷놀이(17825) 문제이다.

[ 문제 바로가기 ]

(설명이 굉장히 길어요 ! )

[ 문제풀이 ]

1) 굉장히 까다로웠던 문제이다. 먼저, 문제를 해결하는데 큰 도움이 될만한 몇 가지 정보를 알아보고 어떻게 구현할지

   알아보도록 하자.

   문제에서 주어진 맵이다. 지금부터는 설명을 보다 편하게 하기 위해서, 위의 맵에 표시를 한 것 처럼

   파랑 동그라미로 주어진 칸을 저렇게 순서대로 '1', '2', '3'번으로 번호를 붙이고 저 번호로 지금부터 계속

   말을 할 것이다.

   가장 먼저, 시작점에서 도착점을 갈 수 있는 경로가 총 몇개가 있을까 ? 바로 4개가 있다. 다음과 같이

  

    이렇게 빨간줄, 파랑줄, 초록줄, 주황줄 4개의 경로가 존재한다. " 경로 = 4개 존재 ! "

    너무 쉬운 질문이었으니 조금 어려운 질문으로 들어가보자. 그렇다면, 맵에서 시작 -> 도착점으로 갈 때,

    파랑 동그라미(1, 2, 3번)들 중, 2개 이상의 파랑 동그라미에서 시작할 수 있을까 ??

    정답은 없다 이다.

    빨강색 루트를 보면, 1번 원에서 한번 시작했었다. 그 이후로, 2번 3번 동그라미에서 시작할 수가 없는 경로이다.

    파랑색 루트를 보면, 1번 원을 그냥 지나치고, 2번 원에서 시작했었다. 그 이후로, 1번 3번 동그라미를 지나치지도

    시작하지도 않았다.

    초록색 루트를 보면, 1번, 2번 원을 그냥 지나치고 3번 원에서 시작했다. 그 이후로, 1번 3번 동그라미를 지나치지도

    시작하지도 않았다.

    주황색 루트를 보면, 1번 2번 3번 원을 그냥 지나치고 도착점에 도달하였다.

    즉, 파랑색 원에서 시작하는 경우가 '1'번 있거나 없을수는 있어도 절대로 2번 이상일 경우는 없다는 것이다.

    " 파랑색 원들 중에서 하나의 원에서 한번 시작하거나, 시작하는 경우가 없을수는 있지만, 절대로 2번 이상

      시작하는 경우는 존재하지 않는다. "

    이번에는 각 경로로 갈때 몇번 움직여야 도착점에 도착할 수 있는지를 알아보자.

    직접 세보면 된다. 빨간경로 = 13번 이상 , 파랑경로 = 17번이상 , 초록경로 = 23번 이상, 주황경로 = 21번 이상

   

    그렇다면, 이번에는 문제의 조건 하나를 생각해보자. "이동하려는 칸에 말이 존재하면, 그 칸으로 움직일 수 없다"

    라는 조건이 있다.

    하지만 우리는 이미 경로를 알고 있잖아 ? 빨간경로 , 파랑경로 , 초록경로, 주황경로 다 나눠져 있는데

    각각의 색깔에 맞는 경로로 움직일 때 해당 칸에 말이 있는지만 체크해 주면 되지 않을까 ??

   예를 들면  "내가 현재 빨간경로로 움직이는데 7칸을 움직일 것이다. 움직일 수 있나?" 를 물을 때,

   빨간 경로로 7칸을 움직인 "16"번을 체크해봐야겠다 !  이런식이다.

   이러면 틀리게 된다. 왜 ?? 도착점과 일직선에 있는 "25 , 30, 35, 40" 좌표를 보자.

   정말 안타깝게도 "25, 30, 35"는 빨강, 파랑, 초록경로 모두 지나는 점이고, "40"은 주황점까지 지나는 점이다.

   조금만 더 생각해보면 시작점과 일직선에 있는 "2, 4, 6, 8, 10" 도 모든 경로들이 공통되게 지나는 점들이다.

   지금부터 위에서 말한 빨강 , 파랑, 초록, 주황색 경로들 이 겹치는 점들을 "특별한 점"이라고 표현해보겠다.

   우리는 위에서 말한 문제의 조건을 해결하기 위해서 다음과 같은 판단을 해줘야 한다.

   "이동하려는 점이 특별한 점인지 아닌지".

   만약, 특별한 점이 아니라면, 해당 경로에서 계산했을 때 말이 있는지 없는지만 판단해 주면 되지만,

   특별한 점이라면, 해당 경로 뿐만 아니라 다른 경로에서 움직이는 말에 의해서 중복되는지 아닌지를 판단해

   주어야한다.  

   이건, 구현 할 때 편하게 하기 위해서 쓰는 내용이다.

   빨강 , 파랑, 초록 경로가 겹치는 { 25, 30, 35, 40 } 을 "각 경로별 움직여야 하는 칸수"로 적어본다면

   빨강경로 = { 9, 10, 11, 12 }

   파랑경로 = { 13, 14, 15, 16 }

   초록경로 = { 19, 20, 21, 22 } 가 된다.

   즉, 1번 원에서 시작한 적이 있고, 9칸을 움직이려고 한다면, 체크해줘야 할 것이

   2번 원에서 시작한 적이 있고, 13칸을 움직인 놈이 있는지, 3번 원에서 시작한 적이 있고, 19칸을 움직인 놈이 있는지

   를 판단해 줘야 한다. 물론, 1번 원에서 시작하고 9칸을 움직인 놈은 당연히 것이다.

   즉, Visit[1][x] 를 갈 수 있는지 판단하기 위해서는, Visit[2][x+4], Visit[3][x+10] 을 판단해 주어야 한다.

   물론 ! 특별한 점일때이다. 이부분은 잘 모르겠어도 그냥 넘어가자. 코드를 보면 이해가 갈 것이다.

2) 그렇다면 위의 정보들을 토대로 간단하게 생각을 해보자.

   어떤 A라는 말이 현재 6칸을 움직였다. 이 말은 어디에 위치하고 있는 것일까 ??

   알 수가 없다. 5칸 + 1칸이 나왔다면, 빨강색 루트에 있는 '13'에 위치할 것이고, 3칸 + 3칸이 나왓다면, 1번 원을

   그냥 지나치고 '12'에 위치할 것이다.

   그렇다면 현재 말이 파랑색 원들 중 몇 번 원에서 시작했는지 알고 있다면 ?? 6칸을 움직였다 라는 말만 들어도

   어디에 위치하고 있는지 알 수 있을 것이다.

   예를 들어서 현재 말은 "1번 원에서 시작을 한번 했고, 6칸을 움직였습니다." 라고 하면, "13"에 있을 것이고

   현재 말은 "아직 파랑색 원들 중 어떤 원에서도 시작한 적이 없고, 6칸을 움직였습니다" 라고 하면 "12"에 있을 것이다.

   하나만 더 해보자. 현재 말이 "3번 원에서 시작을 한 적이 있고, 17칸을 움직였습니다." 라고 하면 어디에 있을까?

   초록색 경로를 따라간 "27번"에 위치해 있을 것이다.

   그런데, 현재 말이 "2번 원에서 시작을 한 적이 있고, 17칸을 움직였습니다." 라고 하면 ?

   파랑색 경로를 따라가 이미 도착점에 도착 해 있을 것이다.

   이러한 계산이 가능한 이유가 뭘까 ?? 이유라고 하기도 좀 그렇다. 당연한거니까... 하지만 굳이 이유를 말해보자면

   위에서 말한 "파랑색 원들 중에서 하나의 원에서 한번 시작하거나, 시작하는 경우가 없을수는 있지만, 절대로 2번 이상

   시작하는 경우는 존재하지 않는다." 라는 정보를 알고 있기 때문이다.

   극단적으로, 위의 정보를 모르고 있었을 때 "3번 원에서 시작을 한 적이 있고 ,17칸을 움직였습니다." 라는 말을

   들었다면, "1번 원에서도 시작을 했는지 안했는지 모르는데 어떻게 알아 ? " 혹은 "2번 원을 그냥 지나쳤는지 2번 원에서

   시작했는지 모르는데 그걸 어떻게 알아 ? "라는 생각을 할 수가 있다.

3) 이제 어느정도 정보를 알았으니 문제를 풀기 전에 ! 어떤 변수들을 이용해서 어떻게 체크를 해주는지, 어떻게 점수를

   계산해줬는지에 대해서 알아보자.

   먼저, 본인은 맵을 만들어 주었다. 위의 그림을 어떻게 맵으로 표현할까 ??

   바로 경로로 나눠주었다. 우리는 도착점에 도달하기 위해서는 총 4개의 경로가 있다는 것을 알고 있다.

   즉, MAP_Score[4][30] 으로 맵을 선언해 주었다.

   크기가 왜 4랑 30일까 ? 앞에 4는 경로를 의미한다.

   0 = 파랑 원에서 시작한 적이 없습니다.

   1 = 1번 원에서 시작한 적이 있습니다.

   2 = 2번 원에서 시작한 적이 있습니다.

   3 = 3번 원에서 시작한 적이 있습니다.

   위와 같은 계산을 할 수 있던 것도, 우리가 미리 파악한 정보인 "단 하나의 파랑색 원에서만 시작할 수 있다" 라는 사실을

   알고 있기 때문이다.

   그렇다면 왜 30일까 ?? 위에서 각 경로로 갈 때 움직여야 하는 횟수를 계산했었다.

   빨강경로 = 13, 파랑경로 = 17, 초록경로 = 23, 주황경로 = 21 이 정보이다.

   이 때, 최대한 많이 움직였을 경우라고 하면 아마 초록경로에서 22번 움직였을 때 5번을 더 움직이는 경우일 것이다.

   즉, 움직일 수 있는 최대 칸의 갯수는 27칸이라는 것이다. 그래서 이 값을 통해서 보다 넉넉하게 30으로 설정해 주었다.

   그럼 이 맵에 점수를 넣어보자.

   MAP_Score[1][7] 은 얼마일까 ? 이는 "1번 원에서 시작한 적이 있고, 지금까지 총 7칸을 움직였습니다." 이다.

   즉, MAP_Score[1][7] = 16이다.

   MAP_Score[2][15] = ?? 35이다.

   칸수를 잘 세면서 점수를 실수하지 않고 잘 작성해보도록 하자.

  

   두 번째는,  위에서 말한 "특별한 점"들을 표시하는 2차원 배열을 하나 만들어주었다.

   범위는 마찬가지로 Special_Point[4][30]이다. 특별한 점에 포함되는 좌표들은 위에서 말했듯이 겹치는 경로들이다.

   Special_Point[a][b] = true 의 의미는, "a번 원에서 시작한 적이 있고, 현재 b칸을 움직였을 때의 좌표는 특별한 점입니다"

   이다. 몇 가지만 예를 들어주자면 Special_Point[1][9] , Special_Point[3][20] , Special_Point[0][20], Special_Point[2][16]

   모두 true 값을 가지는 특별한 점들이다.

   세 번째는, 각각의 경로를 이동할 때 , 도착점에 도착하기 위한 최대 칸수를 저장해놓은 배열이다.

   왜냐하면, 도착했는지 안했는지를 판단해야 하기 때문이다. 예를 들어서 빨간 경로로 갈 때, 20칸을 움직였다 ! 라는 것은

   애초에 말이 안되기 때문이다. 빨간 경로로 갈때는 13칸만 움직이더라도 이미 도착한 상태가 되어버린다.

   Move_Num[4] = { 21, 13, 17, 23 } 으로 설정해 주었다.

  

   네 번째는, 윷의 상태를 관리하는 구조체이다.

   구조체에서 관리하는 멤버변수로는 { 윷의 위치 , 윷이 시작한 파랑원의 번호 , 점수 , 도착여부 } 가 있다.

   마지막으로, 움직임에 대한 상태를 받아오는 구조체이다.

   이 구조체는 밑에서 설명하도록 하겠다.

4) 문제를 진짜 풀자 이제 !

   먼저, 본인은 중복순열을 구현해 주었다. 왜 중복순열일까 ?? 움직여야 하는 칸수만큼 4개의 말 중에 하나를

   움직여 줘야 하는데, 그 움직일 때의 순서를 정해주기 위함이다.

   중복인 이유는, 1번 말이 한번 움직였다고 그 다음에는 못움직인다 ! 가 아니기 때문이다. 1번말만 10번 움직일 수도

   있다.

   순열인 이유는, 순서에 따른 결과가 달라지기 때문이다.

   예를 들어서 입력이 { 3, 4, 2, ..... } 이런식으로 주어졌고 중복순열로 구현한 말의 번호가 { 1, 2, 1 ... } 이 나온 경우와

   { 1, 1, 2 ... } 가 나온 경우를 비교해보면 결과가 달라진다는 것을 알 수 있다. 즉, 순서에 영향을 미친다 !

   중복 순열을 잘모른다면 아래의 글을 읽고 오도록 하자.

   [ 중복순열 알아보기(Click) ]

  

5) 지금부터는 중복순열로 윷을 뽑는 과정에서 고려해줘야 할 부분에 대해서 생각해보자.

   첫 번째는 현재 윷이 끝났는지에 대한 여부이다.

   만약, 현재 윷이 이미 도착점에 도달한 상태라면, 그 윷을 또 움직이는 것은 말이 안되는 것이기 때문이다.

   두 번째는 현재 윷을 이동하려는 칸 만큼 움직일 수 있는지에 대한 판단이다.

   현재 윷이 이동하려는 칸에 이미 다른 윷이 있다면 그 윷은 움직일 수 없기 때문이다.

   첫 번째 조건은 매우 간단하다. 위에서 말한 윷 구조체 배열에 'Finish'라는 변수를 통해서 쉽게 판단가능하기 때문이다.

   문제는 두 번째 조건이다. 이동하려는 칸에 대한 정보를 받아와야 하기 때문이다.

   본인은 이 정보를 저장할 수 있는 구조체를 하나 만들었다. 이게 위에서 말하지 않은 "움직임에 대한 상태를 받아오는

   구조체"이다.

   해당 구조체에서 관리하는 멤버변수는 다음과 같다.

   1. 현재 칸

   2. 이동하려는 칸

   3. 이 윷이 시작한 파랑색 원의 번호

   4. 이번 턴의 움직임으로, 파랑색 원이 시작되었는지 아닌지 여부

   5. 이번 턴의 움직임으로, 도착점에 도달 가능한지에 대한 여부

   1번 2번은 넘어가고 3번 4번 5번 변수들에 대해서 구체적으로 생각을 해보자.

  

   3. 이 윷이 시작한 파랑색 원의 번호 이다.

   - 이 변수 같은 경우, 만약 이번 턴의 이동이 아닌, 이미 어떤 파랑색 원을 지났다면 갱신되지 않는다.

     예를 들어서, 현재 A번 윷이 "1번 원에서 시작한 적이 있고, 6칸을 움직였습니다" 라고 한다면,

     당연히 기존에 1번 원에서 시작한 적이 있다는 것을 알고 있기 때문에 이번 턴에서 저 사실이 변하지는

     않기 때문에 저 값이 변하지는 않는다.

     하지만, 5번 움직이고, 2번 움직이는 경우를 생각해보자.

     처음 5번을 움직였을 때는, 아직 1,2,3번 원 중에서 어떤 원에서 시작한지 정해지지 않은 상태이다. 물론,

     도달할 때까지 어떤 원을 지나질도 모르는 상태이다.

     이 때, 2칸을 움직이게 되면 ? 1번 파랑색 원에서 시작했다는 것을 의미하고, 값을 갱신하게 된다.

     그럼 내가 지금 파랑색 원에서 시작하는지 안하는지 어떻게 알아 ??

     바로 1번 멤버변수인 "현재 칸"과 "기존의 파랑색 원의 번호"를 통해서 알 수 있다.

     위에서 말한 이야기지만, 기존의 파랑색 원의 번호가 0이 아니라면 이 변수는 쳐다볼 필요가 없다.

     바뀌지도 않을 것이고 바꿀 필요도 없는 것이다.

     그런데, 기존의 파랑색 원의 번호가 0일 경우이다. 이 말은, "아직까지 파랑색 원에서 시작한 적이

     없어요" 라는 말이다.

     이 때, 현재 칸이 5 , 10, 15 3개중에 하나라면, 파랑색 원에서 시작한다는 것을 의미한다.

     5, 10, 15가 어디서 나온 값이냐 ?! 맵에서 직접 세보면 된다. 1번 파랑색 원은 5칸을, 2번 파랑색원은

     10칸을, 3번 파랑색원은 15칸을 움직이면 나오는 칸수이다.

   4. 이번턴의 움직임으로, 파랑색 원이 시작되었는지 아닌지에 대한 여부

   - 이게 뭘 의미하는 걸까 ?? 바로 현재 턴에서의 움직임으로 인해 파랑색 원이 결정되었냐를 표시해주는 변수이다.

     예를 들어서 A번 윷이 시작점에서 3칸 , 4칸을 움직였다. 저 2번의 움직임 중에서 결정된 파랑색원이 있을까 ?

     없다. 그런데 5칸, 2칸을 움직일 경우, 2칸을 움직일 때, 파랑색 원이 1번 원으로 결정된다.

     그럼 이게 왜 필요할까 ??

     바로 백트래킹 부분 때문이다. 우리가 지금 하고 있는 것은 "중복순열로 나올 수 있는 모든 경우를 탐색해서

     최대점수 구하기" 를 하고 있는 것이다. DFS특성 상, 완전탐색을 하기 위해서 이미 실행한 것에 대한 취소하는

     부분도 필요하다. 예를 들면 이런 경우이다. 현재 턴에서 나는 A번 윷을 3칸 움직였을 때 결과값이 a 였다.

     그런데 B번 윷을 3칸 움직였을 때의 결과를 알기 위해서는, B번 윷을 3칸 움직일 뿐더러, A번 윷을 다시 3칸 앞으로

     옮기는, 즉 실행을 취소하는 부분이 필요하다.

     이 부분을 구현하기 위해서이다.

     취소할 때, 단순히 칸 수만 움직인 만큼 되돌려 놓으면 될까 ? 아니다. 고려해야 될게 생각보다 굉장히 많다.

     고려해야 될 것에 대한 리스트는 밑에서 정리하고 지금은 이 변수의 필요성에 집중해보자.

     고려해야 될 것들 중 하나가 "현재 턴에서 파랑원이 결정됬냐" 이다.

     또 예를 보면서 이해해보자.

     시작점에서 5칸 , 2칸 , 2칸을 움직인 윷 A가 있다. 이 때 우리는 마지막 2칸을 실행 취소 시키고 싶다.

     그럼 우리가 지금까지 알고 있는 사실은 5칸 , 2칸을 움직이면서 "1번 원에서 시작을 했구나 !" 와

     MoveNum[1] = 13 이기 때문에, 5 + 2 + 2를 해봤자 9이기 떄문에 아직 도착하지 않았구나 ! 를 알 수 있다.

     이 때, 마지막 2칸을 실행 취소 시키면 ? 위치가 2칸 앞으로 가는 것은 당연한 것이고, 이 과정에서

     파랑색 원에 대한 정보가 변할까 ?? 변하지 않는다.

     그렇다면 이런 경우를 생각해보자. 5칸 2칸 움직인 윷 A에서 마지막 2칸을 실행 취소 시키고 싶다.

     그럼 우리는 처음 5칸을 움직인 후, 2칸을 움직일 때, 파랑색원이 1번으로 결정된다.

     왜냐하면 위에서 말했듯이 "현재칸 = 5" 이고 "기존에 정해진 파랑원의 번호 = 0" 이기 때문이다.

     근데 이 2칸을 취소해버리면 ?? 2칸 앞으로 가는것은 물론, 파랑색 원의 정보 또한 사라지게 된다.

     즉 ! 상황에 따라서 파랑색 원의 정보가 변할수도, 변하지 않을 수도 있따는 것이다.

     더 나아가서는, 이번 턴에 윷이 끝났다면, 실행 취소 시, 윷이 끝나지 않았다는 것 또한 표시해 주어야 한다.

     이러한 부분 때문에 "현재의 움직임으로 인해서, 파랑색 원이 결정되었나요 ?" 를 확인하기 위해서

     이와 같은 변수를 설정해 주었다.

   5. 이번 턴으로 인해서 윷이 도착점에 도달하였는지에 대한 여부

   - 4번과 굉장히 비슷한 맥락이다. 현재의 움직임으로 인해, 윷이 끝났다면, 이 움직임을 취소하는 순간

     윷이 끝나지 않은 것으로 표시를 해줘야 한다.

   이렇게 구조체를 만들어서 "현재의 움직임에 대한 정보"를 받아왔다.  

  

말이 굉장히 많았고, 설명한만큼 생각할 것도 구현할 것도 많은 까다로운 문제인 것 같다.

소스코드와 함께 설명을 잘 읽어보면서 풀어보자 !

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
struct STATE            // 움직임에 대한 정보를 받아오는 구조체
{
    int Prev;            // 현재 칸
    int Next;            // 이동하려는 칸
    int Start_Circle;    // 시작한 파랑원의 번호(1, 2, 3 중 하나)
    bool Select_Circle;    // 이번 움직임으로 파랑색 원의 번호가 결정되었는지에 대한 여부판단
    bool Finish;        // 이번 움직임으로 윷이 도착점에 도달하였는지에 대한 여부판단
};
 
struct YUT
{
    int Blue_Circle;    // 윷이 한번이라도 시작한 파랑색 원의 번호
    int Pos;            // 윷의 정보
    int Score;            // 윷의 점수
    bool Finish;        // 윷이 도착점에 도달했는지에 대한 여부
};
 
int Answer;
int Command[MAX];
int MoveNum[4];                // 각 경로 별, 움직여야 하는 최대 칸수를 저장하는 배열
int MAP_Score[4][30];        // 점수 판
bool Visit[4][30];            // 이미 다른 윷이 있는지 없는지 판단하기 위한 배열
bool Special_Point[4][30];    // 특별한 점 (모든 경로가 겹치는 칸들)
 
YUT Yut[4];
 
void Setting()
{
    /* 기초 세팅 작업 */
    /* 
    1. 각 경로 별 움직여야 하는 최대 칸수를 저장하는 배열 Move_Num에 값 삽입.
       2. 특별한 점들 체크.
       3. 점수 판 만들기
    */
    MoveNum[0] = 21;
    MoveNum[1] = 13;
    MoveNum[2] = 17;
    MoveNum[3] = 23;
 
    Special_Point[1][9] = Special_Point[1][10] = Special_Point[1][11] = Special_Point[1][12] = true;
    Special_Point[2][13] = Special_Point[2][14] = Special_Point[2][15] = Special_Point[2][16] = true;
    Special_Point[3][19] = Special_Point[3][20] = Special_Point[3][21] = Special_Point[3][22] = true;
    Special_Point[0][1] = Special_Point[0][2] = Special_Point[0][3] = Special_Point[0][4] = Special_Point[0][5] = Special_Point[0][20] = true;
 
    for (int i = 1; i <= 20; i++) MAP_Score[0][i] = 2 * i;
    MAP_Score[1][6] = 13; MAP_Score[1][7] = 16; MAP_Score[1][8] = 19; MAP_Score[1][9] = 25;
    MAP_Score[1][10] = 30; MAP_Score[1][11] = 35; MAP_Score[1][12] = 40;
    MAP_Score[2][11] = 22; MAP_Score[2][12] = 24; MAP_Score[2][13] = 25; MAP_Score[2][14] = 30;
    MAP_Score[2][15] = 35; MAP_Score[2][16] = 40;
    MAP_Score[3][16] = 28; MAP_Score[3][17] = 27; MAP_Score[3][18] = 26; MAP_Score[3][19] = 25;
    MAP_Score[3][20] = 30; MAP_Score[3][21] = 35; MAP_Score[3][22] = 40;
 
    for (int i = 1; i <= 5; i++) MAP_Score[1][i] = MAP_Score[0][i];
    for (int i = 1; i <= 10; i++) MAP_Score[2][i] = MAP_Score[0][i];
    for (int i = 1; i <= 15; i++) MAP_Score[3][i] = MAP_Score[0][i];
}
 
void Input()
{
    for (int i = 0; i < 10; i++) cin >> Command[i];
}
 
STATE GetState(int Idx, int C_Idx)
{
    /* 현재의 움직임으로 변하는 윷의 상태를 받아오는 함수 */
    int Prev = Yut[Idx].Pos;                    // 윷이 현재 있는 칸
    int Next = Yut[Idx].Pos + Command[C_Idx];    // 윷이 이동하려는 칸
    int Start_Circle = Yut[Idx].Blue_Circle;    // 기존에 시작한 파랑색 원의 번호
    bool Select_Circle = false;                    // 이번 턴의 움직임으로 인해 파랑색 원이 결정되었는지에 대한 여부
    bool Finish = false;                        // 이번 턴의 움직임으로 인해 도착점에 도달했는지에 대한 여부
 
    if (Start_Circle == 0)                        // 아직 시작한 파랑색 원이 없을 경우에만
    {
        if (Prev == 5 || Prev == 10 || Prev == 15)    // 파랑색 원에서 시작한다면
        {
            Select_Circle = true;                // 이번 턴의 움직임으로 파랑색 원이 결정되었다.
            Start_Circle = Prev / 5;            // 윷의 시작한 파랑색 원의 번호
        }
    }
 
    if (Next >= MoveNum[Start_Circle]) Finish = true;    // 도착점에 도달했다면 체크.
 
    return{ Prev, Next, Start_Circle, Select_Circle, Finish };
}
 
bool Check_Special_Point(int Circle, int Pos)
{
    /* 특별한 점에 다른 윷이 존재하는지 판단하는 함수 */
    if (Circle == 0)
    {
        /* 현재 이동하려는 윷이 파랑색 원에서 시작한 적이 없는 경우. */
        /* '40'점이 설정되어있는 칸에 기존에 윷이 있는지 판단해 주면 된다.
        /* '40'점이 있는 칸은, 빨강색, 파랑색, 초록색, 주황색 모두 겹치는 경로이기 때문 ! */
        if (Pos == 20)
        {
            if (Visit[1][12] == true || Visit[2][16] == true || Visit[3][22] == true) return false;
        }
        else
        {
            if (Visit[0][Pos] == true) return false;
        }
    }
    else if (Circle == 1)
    {
        /* 현재 윷이, 1번 파랑 원에서 시작해서 움직이고 있는 경우 */
        /* 빨강색 / 파랑색 / 주황색 경로가 겹치는 "25", "30", "35", "40" 을 체크해 주어야 한다. */
        if (Visit[2][Pos + 4] == true || Visit[3][Pos + 10] == true) return false;
        if (Pos == 12)
        {
            if (Visit[0][20] == true) return false;
        }
    }
    else if (Circle == 2)
    {
        if (Visit[1][Pos - 4] == true || Visit[3][Pos + 6] == true) return false;
        if (Pos == 16)
        {
            if (Visit[0][20] == true) return false;
        }
    }
    else if (Circle == 3)
    {
        if (Visit[1][Pos - 10] == true || Visit[2][Pos - 6] == true) return false;
        if (Pos == 22)
        {
            if (Visit[0][20] == true) return false;
        }
    }
    return true;
}
 
bool Check_Visit(STATE S, int Idx)
{
    /* 현재 윷이 움직일 수 있는지를 판단해주는 함수 */
    /* 판단해 줘야 할 것
       1. 움직이려는 좌표가 특별한 점인지 ?
          - 특별한 점이라면 다른 경로를 통해서 해당 좌표에 있는 놈들도 Check.
       2. 움직이려는 좌표에 다른 윷이 존재하는지 ? 
    */
    if (Special_Point[S.Start_Circle][S.Next] == true)
    {
        if (Check_Special_Point(S.Start_Circle, S.Next) == false) return false;
    }
 
    if (Visit[S.Start_Circle][S.Next] == true) return false;
    return true;
}
 
void MakeState(STATE S, int Idx, bool T)
{
    /* 방문 체크를 하고, 실제로 윷을 옮기는 함수. */
    /* T = true 일 경우, 실행 */
    /* T = false 일 경우, 실행 취소 */
 
    if (T == true)
    {
        if (S.Finish == true)
        {
            /* 현재 턴의 움직임으로 윷이 도착점에 도달했다면 ?? */
 
            Visit[S.Start_Circle][S.Prev] = false;    // 기존 좌표 방문 체크 해제
            Yut[Idx].Pos = S.Next;                    // 현재 윷의 좌표 갱신
            Yut[Idx].Finish = true;                    // 끝났음을 표시.
            // 마지막 좌표는 윷이 있어도 다른 윷이 올 수 있기 때문에, 해당 좌표에 방문표시는 하지 않음 ! 
        }
        else
        {
            /* 현재 턴의 움직임으로 윷이 도착점에 도달하지는 않은 경우 */
            if (S.Select_Circle == true)
            {
                /* 현재 턴의 움직임으로 파랑원의 번호가 결정 되었다면 ?*/
 
                Yut[Idx].Blue_Circle = S.Start_Circle;    // 윷의 파랑 원의 번호를 설정
                Visit[0][S.Prev] = false;                // 기존의 좌표 체크 해제.
                /* 이번 턴에 파랑원의 번호가 결정되었다 = 기존에는 파랑원이 결정되지 않은 상태였다. 
                   즉, 기존의 좌표 체크 해제는 파랑원이 결정되지 않은 Visit[0][S.Prev]로 해준다.
                */
            }
            else
            {
                /* 현재 턴의 움직임으로 파랑원의 번호가 결정되지 않았다. */
                /* 이미 정해져있었을 수도, 아니면 아직 정해지지 않은 것일수도 있다. */
 
                Visit[Yut[Idx].Blue_Circle][S.Prev] = false;
                /* 기존의 좌표 체크 해제. 파랑원이 기존에 정해졌는지 아직 안정해졌는지는 모르지만 
                   이번 턴에 결정되지는 않았으니까, Yut[Idx].BlueCircle 로 파랑원의 번호를 대체 */
            }
            Visit[Yut[Idx].Blue_Circle][S.Next] = true;    // 방문 체크
            Yut[Idx].Pos = S.Next;                        // 좌표갱신
            Yut[Idx].Score = Yut[Idx].Score + MAP_Score[Yut[Idx].Blue_Circle][S.Next]; // 점수갱신
        }
    }
    else
    {
        /* 실행 취소하는 과정 */
        if (S.Finish == true)
        {
            /* 이번 턴으로 윷이 도착점에 도달했다면 ? */
            Visit[S.Start_Circle][S.Prev] = true;    // 기존의 좌표 방문 체크
            Yut[Idx].Pos = S.Prev;                    // 좌표값 되돌리기
            Yut[Idx].Finish = false;                // 끝남표시 해제
        }
        else
        {
            if (S.Select_Circle == true)
            {
                /* 이번 턴으로 인해서 파랑색 원이 결정 되었는데, 이를 실행취소 한다. */
 
                Visit[0][S.Prev] = true;                        // 기존에는 아직 파랑원이 정해져 있지 않았는데, 그 좌표로 돌아가야 하므로 Visit[0][S.Prev]
                Visit[Yut[Idx].Blue_Circle][S.Next] = false;    
                Yut[Idx].Pos = S.Prev;
                Yut[Idx].Score = Yut[Idx].Score - MAP_Score[Yut[Idx].Blue_Circle][S.Next];
                Yut[Idx].Blue_Circle = 0;    // 선택한 파랑원의 번호 다시 0으로 갱신.
            }
            else
            {
                Visit[Yut[Idx].Blue_Circle][S.Prev] = true;
                Visit[Yut[Idx].Blue_Circle][S.Next] = false;
                Yut[Idx].Pos = S.Prev;
                Yut[Idx].Score = Yut[Idx].Score - MAP_Score[Yut[Idx].Blue_Circle][S.Next];
            }
        }
    }
}
 
void DFS(int Cnt)
{
    if (Cnt == 10)
    {
        int Temp = 0;
        for (int i = 0; i < 4; i++) Temp = Temp + Yut[i].Score;
 
        if (Answer < Temp) Answer = Temp;
        return;
    }
 
    for (int i = 0; i < 4; i++)
    {
        if (Yut[i].Finish == true) continue;
        STATE State = GetState(i, Cnt);
        if (Check_Visit(State, i) == false) continue;
 
        MakeState(State, i, true);
        DFS(Cnt + 1);
        MakeState(State, i, false);
    }
}
 
void Solution()
{
    DFS(0);
    cout << Answer << endl;
}
 
void Solve()
{
    Setting();
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}