[알고리즘] 백준 17825

백준 17825번 주사위 윷놀이

해결 과정 요약

모든 노드와 간선을 미리 추가해 놓는다. 간선을 빼먹지 않도록 주의한다.
함수 3개를 만들어준다.

int shift(int n, int idx, int toggle){
    if(n == 0 || v[idx].size() == 0) return idx;
    else if(v[idx].size() == 2 && toggle){
        return shift(n-1, v[idx][1], 0);
    }
    return shift(n-1, v[idx][0], 0);
}
// idx에 위치한 말이 n만큼 이동했을 때의 인덱스를 리턴.
// 첫 호출에서 toggle을 1로 호출하고 재귀호출시에는 0으로 바꿔준다.   

bool go(int n, int malidx){
    if(mal[malidx] == 32) return -1;
    int sh = shift(n, mal[malidx], 1);
    for(int i=0; i<4; i++){
        if(malidx == i) continue;
        if(mal[i] == sh && mal[i] != 32) {
            return false;
        }
    }
    score += a[sh];
    mal[malidx] = sh;
    return true;
}
// malidx번째 말이 n번 이동할 수 있는지 없는지를 판별하는 함수. shift함수 이용.
// 못간다면 false를 리턴
// 갈 수 있다면 말을 옮기고 score를 늘려준 뒤 true를 리턴

void yut(int cnt){
    if(cnt == 10) { ret.push_back(score); return; }
    for(int i=0; i<4; i++){
        int tmp = score;
        int mal_t[4];
        memcpy(mal_t, mal, sizeof(mal));
        if(!go(dice[cnt], i)) continue;
        else {
            yut(cnt + 1);
            score = tmp;
            memcpy(mal, mal_t, sizeof(mal));
        }
    }
}
// cnt번째 주사위를 던지는 함수. cnt를 1씩 늘려가는 재귀함수다.
// cnt가 10이면 벡터에 점수를 푸시하고 리턴

메인에서 yut(0)을 호출하고 벡터안에 들어있는 값중에 가장 큰 값을 출력하면 된다.

풀이

#include <bits/stdc++.h>
using namespace std;

int score = 0;
int mal[4] = {0,0,0,0};
int dice[10];
int a[33] = {0,2,4,6,8,10,12,14,16,18,
            20,22,24,26,28,30,32,34,36,38,
            40,13,16,19,25,26,27,28,22,24,30,35,0};
vector<int> v[33];
vector<int> ret;

int shift(int n, int idx, int toggle){
    if(n == 0 || v[idx].size() == 0) return idx;
    else if(v[idx].size() == 2 && toggle){
        return shift(n-1, v[idx][1], 0);
    }
    return shift(n-1, v[idx][0], 0);
}

bool go(int n, int malidx){
    if(mal[malidx] == 32) return -1;
    int sh = shift(n, mal[malidx], 1);
    for(int i=0; i<4; i++){
        if(malidx == i) continue;
        if(mal[i] == sh && mal[i] != 32) {
            return false;
        }
    }
    score += a[sh];
    mal[malidx] = sh;
    return true;
}

void yut(int cnt){
    if(cnt == 10) { ret.push_back(score); return; }
    for(int i=0; i<4; i++){
        int tmp = score;
        int mal_t[4];
        memcpy(mal_t, mal, sizeof(mal));
        if(!go(dice[cnt], i)) continue;
        else {
            yut(cnt + 1);
            score = tmp;
            memcpy(mal, mal_t, sizeof(mal));
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    for(int i=0; i<20; i++){
        v[i].push_back(i+1);
    }
    v[5].push_back(21); v[21].push_back(22); v[22].push_back(23); v[23].push_back(24);
    v[24].push_back(30); v[30].push_back(31); v[31].push_back(20); v[10].push_back(28);
    v[28].push_back(29); v[29].push_back(24); v[15].push_back(27); v[27].push_back(26);
    v[26].push_back(25); v[25].push_back(24); v[20].push_back(32);
    
    for(int i=0; i<10; i++) cin >> dice[i];
    
    yut(0);
    sort(ret.begin(), ret.end());
    cout << ret.back();
    
    return 0;
}

트러블슈팅

처음에 풀 때는 가는 길을 여러개로 나눠서 특정노드에서 출발하면 길을 바꿔타는 식으로 구현했었다.
근데 그렇게 했더니 코드는 알아보기 힘들게 길고 go함수의 구현이 힘들어서 위와 같이 그래프와 간선을 사용하는 방식으로 바꾸었다.

또 memcpy의 사용법을 제대로 알고있지 않아서 출려값이 너무 터무니없게 나왔었다.
memcpy를 통해서 말을 이전상태로 바꾸어줘야 완전탐색이 이루어지는데 이것이 제대로 안된거다.
디버깅을 통해 말이 이전상태로 바뀌지 않는것을 발견하고는 memcpy를 고쳤다.

코멘트

요즘 완전탐색과 백트래킹을 공부중인데 아직 dfs할 때 visited를 0으로 바꿔주거나 위 문제와 같이 말을 이전상태로 바꿔주는 등등.. 이런것들이 익숙하지가 않다. 그리고 뭔가 디버깅 하기도 귀찮고 힘든 느낌..