BOJ - 주사위 윷놀이 (17825) [2019 삼성 SW 기출]

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

17825번: 주사위 윷놀이

 

2019년 하반기 삼성 기출문제입니다.

 

이 문제에서 가장 어려운 점은 바로 '디자인'입니다.

도대체 이 윷놀이 판을 어떻게 디자인해야 하는가...?

 

처음 해본다면 굉장히 난해합니다.

 

1. 정사각 배열을 만들어 똑같이 그린다.

2. 원을 하나의 노드라고 생각하고, 그래프로 생각하여 디자인한다.

 

아무래도 directed graph로 생각하고 디자인하는게 훨씬 쉬워 보입니다.

다만, 파란색 노드에서 시작할 때, 다른 방향으로 가게끔 해주는 코드를 작성해주면 됩니다.

 

노드 갯수가 총 33개 정도(?) 되는 것 같네요.

뭐 이정도면 ... 사실 매우 많은 편이긴한데 불가능한 정도는 아니기에 

하나하나 코드로 작성해 줍니다.

 

디자인이 끝났다면, 그 다음은 다른 문제들과 다른 점이 없습니다.

 

바로 '완전 탐색'입니다.

시간 복잡도는 대충 잡으면 4^10 입니다. 약 1000000 입니다. 시간 안에 충분히 가능하죠!

 

제가 임의로 디자인한 내용들을 아래 그림으로 그려봤습니다.

노드 번호를 임의로 배정해주고, adjacent list 를 통해 그래프의 엣지들을 표현해주었습니다.

 

메인 함수 처음에 그래프를 그려주는 부분을 유심히 보고, 아래 그림과 비교해보시면 다음에 이런 문제를 풀 때

어떻게 해야 하는지 감을 잡으실 수 있습니다!

 

 

 

 

#include <iostream>
#include <vector>
#include <string.h>
#include <string>
#include <algorithm>
 
using  namespace std;
 
int v[33][2];
int score[33];
vector<int> yut;    // 윷놀이 10개 결과 받는 변수
int ans;
int pos[5];            // 4개의 말의 현재위치
bool chk[33];        // 현재 노드에 말이 존재하는지를 확인하기 위한 배열
bool change_dir[33];    // 시작 노드가 방향을 바꿔야 하는지 확인하기 위한 배열
 
 
void sol(int cur, int total){
    if(cur == 10){
        ans = max(ans, total);
        return;
    }
 
    int tries = yut[cur];
 
    for(int i = 0; i < 4; i++){
        int tmp = tries;
        int position = pos[i];
        int temp_pos = position;
 
        if(change_dir[position]){
            tmp -= 1;
            position = v[position][1];
        }
 
        while(tmp--) position = v[position][0];
 
        if(position != 21 && chk[position]) continue;    // 21번 노드가 마지막 노드로 세팅되어 있으므로 무시해준다
        // 이곳으로 왔다는 것은 갈 수 있다는 것이다
        // 따라서 chk, pos 배열의 값을 변화시켜, 말의 위치가 변했다는 표현을 해준다
        pos[i] = position;
        chk[temp_pos] = false;
        chk[position] = true;
 
        // 말의 위치를 이동시킨 후 그 다음으로 넘어간다
        sol(cur + 1, total + score[position]);
 
        // 다시 말의 위치를 원래 있었던 곳으로 되돌려 
        chk[position] = false;
        chk[temp_pos] = true;
        pos[i] = temp_pos;
    }
}
 
 
 
 
 
int main(){
    // 각 노드의 그 다음노드 세팅, 즉 이것이 화살표 세팅이라고 보면 된다.
    for(int i = 0; i <= 24; i++){
        v[i][0] = i + 1;
    }
 
    v[21][0] = 21;
 
    v[25][0] = 31;
    v[26][0] = 25;
    v[27][0] = 26;
    v[28][0] = 27;
    v[29][0] = 30;
    v[30][0] = 25;
    v[31][0] = 32;
    v[32][0] = 20;
    
    v[5][1] = 22;
    v[10][1] = 29;
    v[15][1] = 28;
 
    change_dir[5] = change_dir[10] = change_dir[15] = true;            // 이 곳에서 시작하면, 방향을 바꿔줘야하기 때문에 설정해준다.
 
    // 점수세팅
    for(int i = 1; i <= 20; i++) score[i] = 2 * i;
    for(int i = 22; i <= 24; i++) score[i] = 13 + 3 * (i - 22);
    score[25] = 25;
    for(int i = 26; i <= 28; i++) score[i] = i;
    score[31] = 30;
    score[32] = 35;
    score[29] = 22;
    score[30] = 24;
 
    yut.resize(10);
    for(int i = 0; i < 10; i++)
        cin >> yut[i];
    
    
 
    sol(0, 0);
 
    cout << ans <<  endl;
}