[백준] 17825번 윷놀이

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

//주사위
int arr[10];
//현재 말의 위치
int mal[4];
//윷놀이 판; 각 위치에서 이동할 다음 위치를 저장함
int map[35];
//판에서 방향 전환
int turn[35];
//현 위치에 말이 있는지 확인
bool check[35];
//윷놀이 판의 점수
int score[35];
//최종 값
int ans=0;

void dfs(int cnt, int sum){
    if(cnt==10){
        if(sum>ans) ans=sum;
        return;
    }
    for(int i=0; i<4; i++){
        //1. 현재 말의 위치, 이동 할 말의 위치
        int prev=mal[i];
        int now = prev;
        // 움직여야 하는 횟수
        int move = arr[cnt];
        // 방향을 전환해야 하면
        if(turn[now]>0){
            now = turn[now];
            move -=1;
        }
        //2. 주사위만큼 이동
        while(move--){
            now = map[now];
        }
        if(now !=21 && check[now]==true) continue; //끝나지 x, 말이 없으면
        //3. 말 여부, 위치 확인
        check[prev]=false;
        check[now]=true;
        mal[i]=now;
        
        dfs(cnt+1, sum+score[now]);
        mal[i]=prev;
        check[prev]=true;
        check[now]=false;
    }
    
}
int main(){
    fastio;
    for(int i=0; i<21; i++) map[i] = i+1;
    map[21]=21;
    
    
    for(int i=22; i<27;i++) map[i] = i+1;
    map[27] = 20; map[28] = 29; map[29] = 30; map[30] = 25;
    map[31] = 32; map[32] = 25;
    
    turn[5]=22; turn[10]=31; turn[15]=28;
    turn[25]26;
    
    for(int i=0; i<21; i++) score[i]=i*2;
    score[22]=13; score[23]=16; score[24]=19;
    score[31]=22; score[32]=24; score[28]=28;
    score[29]=27; score[30]=26; score[25]=25;
    score[26]=30; score[27]=35;
    
    for(int i=0; i<10; i++) cin>>arr[i];
    dfs(0,0);
    cout<<ans<<'\n';
    return 0;
}

 

 

 

<조건>

• 시작 칸에 말이 4개가 있다
• 파란색 칸에 말이 도착할 시 파란색 화살표 방향으로 이동해야한다.
• 말이 이동을 마치는 칸에 다른 말이 있다면 그 말은 고를 수 없다.
• 말이 이동을 마칠 때마다 칸에 적힌 수가 점수가 추가된다.

<풀이>

1. 윷놀이 판의 인덱스 및 점수판 초기화

 1) 해당 노드에 다음 이동할 노드 번호를 저장 (map 배열)

 2) 방향 전환이 되는 노드를 따로 관리 (turn 배열)

 3) 각각의 노드의 점수를 관리 (score 배열)

 4) 해당 노드에 말이 있는지 없는지 확인 배열 (check 배열)

 

2. DFS 함수 탐사 시작하며 초기 말의 위치 저장

  1) 현재 말의 위치, 말이 도착할 위치, 주사위의 갯수 총 3개의 변수 필요

  2) 예외 처리 : 만약 현재 위치가 변환점이라면, turn 배열을 이용하여 위치 변환

                   : 만약 도착 위치에 다른 말이 있다면 continue;

 

3. 파란색 화살표 지점 도달시 방향 전환

4. 현재 위치가 전환점인지 먼저 확인해서 방향 바꿔놓고, 이동 시작

5. 남은 이동횟수만큼 칸 이동

6. 도착위치가 아닌데, 해당 위치에 말이 있다면 못 놓음

7. 이동가능할 시, 해당 칸에 체크하고 점수 추가해서 재귀 호출

8. Depth가 10까지 도달하여 모든 이동 완료시 해당 점수를 최대와 비교하여 업데이트

<참고>

https://haejun0317.tistory.com/163

https://bloofer.net/65