백준(boj) 17825_주사위 윷놀이 (파이썬, c++)

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

풀이

---

주사위 10개의 턴이 주어지는데, 이를 이용해서 최대 점수를 구하는 문제이다. 완전 탐색 하였다. 요점 1. 말 4개를 가지고 게임을 하는데, 2. 이미 말이 있는 곳은 갈 수 없다. 3. 각 칸에는 점수가 있고 4. 파란색 선이 있는 부분은 파란 방향으로, 그 외엔 빨간 방향으로 가야 한다. 해결책 1. horse 라는 리스트에 [방향, 인덱스]를 표현해서 해결 2. visit 리스트를 이용하여 해결 3. 판에 있는 점수들을 a리스트에 표현하여 해결(a리스트 방향에 따라 셋팅) 4. 방향(d 변수)이랑 인덱스(x 변수)로 빨간 방향 부분이면 거기로 향하게 함 a 리스트를 그림으로 표현하면 다음과 같다.

python3

from sys import*
input = stdin.readline
def solve(pos, score):  #pos -> 몇 번째 주사위인지
    global horse, visit
    res = 0
    if pos == 10:return score
    b = [x[:] for x in horse]
    c = [x[:] for x in visit]
    for i in range(4):
        d, x = horse[i]       #방향, 인덱스
        prev_dice = dice[pos]
        nd = d
        nx = x + prev_dice
        if x == INF: continue
        if d == 0 and (x in [5,10,15]):     #d가 0이고(테두리), 확인할 index가 내부에 들어갈 인덱스면
            nd = x // 5                     #만약 idx가 5면 d=1, 10이면 d=2, ...
            nx = prev_dice
        if nd == 0 and nx == 20:            #d==0, x==20 이랑 d==4, x == 3 이랑 칸 중복되어서 따로 처리
            nd = 4
            nx = 3
        if nd in [1,2,3] and (len(a[nd]) <= nx):   #1,2,3 크기 넘어 갈 때
            nx = nx - len(a[nd])
            nd = 4
        if len(a[nd]) <= nx:                #도착, d=1,2,3일 때 넘은건 위에서 이미 처리됨(21 line)
            horse[i] = [0, INF]
            visit[d][x] = 0
            res = max(res, solve(pos+1, score))
        else:
            if visit[nd][nx]: continue
            horse[i] = [nd, nx]
            visit[nd][nx] = 1
            visit[d][x] = 0
            res = max(res, solve(pos+1, score + a[nd][nx]))
        horse=[x[:] for x in b]
        visit=[x[:] for x in c]
    return res

a=[[2*i for i in range(21)]]             # a[0] => 테두리
a.append([10, 13, 16, 19])  # a[1] => 5번째칸 갈 시 이동방향
a.append([20, 22, 24])      # a[2] => 10번째칸 갈 시 이동방향
a.append([30, 28, 27, 26])  # a[3] => 15번째칸 갈 시 이동방향
a.append([25, 30, 35, 40])  # a[4] => 내부에서 중복되는 놈들 처리 안해주면 visit 방문처리가 잘 안됨

INF = 1e9
dice = list(map(int,input().split())) #이동할 주사위 정보
visit=[[0]*21 for _ in range(5)]#1차:방향, 2차:인덱스
horse=[[0,0] for _ in range(4)] #1차:말 번호, 2차: [방향, 인덱스]
print(solve(0, 0))

C++

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<memory.h>
using namespace std;
const int INF = int(1e9);
int a[5][21], visit[5][21], dice[10];
int horse[4][2];

int solve(int pos, int score){
    int res = 0;
    if(pos == 10) return score;
    int b[4][2], c[5][21];
    memcpy(b, horse, sizeof(horse));
    memcpy(c, visit, sizeof(visit));
    for(int i=0; i<4; i++){
        int d, x;
        int &hrd = horse[i][0], &hrx = horse[i][1];
        d = hrd;
        x = hrx;
        int prev_dice = dice[pos];
        int nd, nx;
        nd = d;
        nx = x + prev_dice;
        if(x==INF) continue;
        if(d == 0 && (x==5 || x==10 || x==15)){
            nd = int(x/5);
            nx = prev_dice;
        }
        if(nd==0 && nx==20){
            nd = 4; nx = 3;
        }
        if (((nd==1 || nd==3) && nx >= 4) || (nd==2 && nx >= 3)){
            if(nd == 1|| nd==3) nx = nx - 4;
            else if(nd == 2) nx = nx - 3;
            nd = 4; 
        }
        if((nd==0 && nx >= 21) || ((nd==1 || nd==3 || nd==4) && nx>=4) || (nd == 2 &&  nx >=3)){
            hrd = 0;
            hrx = INF;
            visit[d][x] = 0;
            res = max(res, solve(pos+1, score));
        }
        else{
            if (visit[nd][nx]) continue;
            hrd = nd;
            hrx = nx;
            visit[nd][nx] = 1;
            visit[d][x] = 0;
            res = max(res, solve(pos+1, score + a[nd][nx]));
        }
        memcpy(horse, b, sizeof(b));
        memcpy(visit, c, sizeof(c));
    }
    return res;
}

int main(){
    memset(visit, 0, sizeof(visit));
    memset(horse, 0, sizeof(horse));
    for(int i=0; i<21; i++) a[0][i]=i*2;
    int temp[4][4]= {{10, 13, 16, 19},
                      {20, 22, 24},
                    {30, 28, 27, 26},
                    {25, 30, 35, 40}};
    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++)
            a[i+1][j] = temp[i][j];
    }
    for(int i=0; i<10; i++) scanf("%d", &dice[i]);
    printf("%d",solve(0,0));
    return 0;
}
//20.04.27 v[0][21], v[4][3]겹치는 부분 안겹치게 보완함
#include<cstdio>
#include<algorithm>
#include<memory.h>
#include<vector>
using namespace std;
vector<int> v[5];
const int INF = 1e9;
int horse[4][2], turn[10];
bool isNext(int nd, int nx){
    return v[nd].size() <= nx;                     //nx 더 커서 다음으로 가야하면  true, 아니면 false 반환 
}
int solve(int pos, int score){
    int res = 0;
    if(pos == 10) return score;
    int b[4][2];
    memcpy(b, horse, sizeof(horse));
    for(int i=0; i<4; i++){                        //모든 말들 탐색 
        if(horse[i][0] != INF){                    //도착하지 않은 말들만 처리 
            int d, x, nd, nx;
            d = horse[i][0], x = horse[i][1];
            //방향에 따른 nd, nx 처리
            nx = x + turn[pos];
            nd = d;
            if(d==0 && (nx%5==0)){                 //파란 원 
                nd = nx/5;
                nx = nx!=20? 0: 3;                 //0->4로 가는 경우는 {25, 30, 35}건너 뛰고{40}으로 
            }
            else if((d!=4) && isNext(d, nx)){      //안쪽 빨간 방향 
                nd = 4;
                if(d==0) nx=INF;                   //v[0]인데 넘으면 도착
                else nx = nx - v[d].size();        
            }
            //전처리한 nd, nx 가지고 다음 방문 처리 
            if(isNext(nd, nx)){                    //도착 
                horse[i][0]=INF;
                res = max(res, solve(pos+1, score));
            }
            else{                                  //도착 아니면 말 확인, 
                bool f = false;
                for(int j=0; j<4; j++)
                    if(horse[j][0]==nd && horse[j][1]==nx){
                        f=true;
                        break;
                    }
                if(f) continue;                    //가려고 하는 곳에 이미 말 있으면 다음으로 
                horse[i][0] = nd, horse[i][1] = nx;
                res = max(res, solve(pos+1, score+v[nd][nx]));
            }
            memcpy(horse, b, sizeof(b));
        }
    }
    return res;
}
int main(){
    for(int i=0; i<20; i++) v[0].push_back(i*2);
    v[1] = {10, 13, 16, 19};
    v[2] = {20, 22, 24};
    v[3] = {30, 28, 27, 26};
    v[4] = {25, 30, 35, 40};
    for(int i=0; i<10; i++) scanf("%d",&turn[i]);
    memset(horse, 0, sizeof(horse));
    printf("%d",solve(0, 0));
    return 0;
}

고찰

---

1. nx, x, idx 변수 사용했다가 idx랑 x착각해서 어디서 틀린지 모르고 며칠 고생함.. 변수 설정 유의하기.

2. a 리스트로 표현했지만 겹치는 부분들 ex) d==0, x==20 인곳과 d==4, x==3인곳 visit 처리 안돼서 틀림 겹치는 부분들 처리할 때 일관되게 처리하도록 연습하기