백준 g2 17825 주사위 윷놀이 c++

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

17825번: 주사위 윷놀이

 

문제 설명

• 말은 시작 칸에 총 4개
• 파란색 칸에 멈추면, 파란색 화살표를 따라 가야 함
• 말이 이동을 마치는 칸(도착점)에 다른 말이 있으면 X
• 말이 이동을 마칠 때마다 칸에 적혀 있는 수가 점수로 추가됨
• 주사위에서 나올 수 10개가 주어질 때, 얻을 수 있는 점수의 최댓값

 

풀이

1.주사위 판 짜기

빨간 화살표만 따라갔을 때 경로 0,

10에 도착한 경우 경로 1,

20에 도착한 경우 경로 2, 

30에 도착한 경우 경로 3 로 board[4][25]를 지정했다.

 

주의해야 할 점은 경로 1~3에서 (25, 30, 35, 40)은 공유한다는 점이다. 해당 board에 말이 있는지 없는지 검사할 때 (25, 30, 35, 40)은 공통으로 자리를 써야함을 유의해야 한다.

 

나는 그래서 board의 idx를 비교하는 것에서 board 위 숫자를 비교하도록 코드를 다시 짰는데, 12, 16, 18, 22, 24, 26, 28, 30 이 겹치므로 이 방법은 따로 예외처리를 해주는 거 아니면 쓸 수 없다. (가능은 함)

 

2. 말 움직이기

move(i, j, d) // i: 현재 어떤 경로 위인지, j: 경로 상 인덱스, d: 몇 칸 움직일 지
	if j + d >= 해당 board의 endIdx
    	return (i, endIdx)
    nj = j+d
    if i==0 && nj == 5 or 10 or 15
    	파랑 경로로 옮기기
    else
    	return (i, nj)

 

 

3. 몇 번째 말을 쓸 지 dfs

dfs: k(0~9)번째 주사위에 무슨 말을 움직일 지

dfs(int k)
	if k == 10
    	mx 값 구하기
        return
    for(p: 0~3) // 0~3번째 말(piece) 하나씩 움직여보기
    	if depart[p] 이미 도착했다면 continue
        
        ni, nj = move(i, j, dice[k])
        
        if ni, nj 자리에 이미 누가 있고, 그게 도착점이 아니라면
        	continue
        if ni, nj가 도착점이면
        	depart[p] = true
            
        loc[p] = ni, nj
        score += board[ni][nj]
        
        dfs(k+1)
        
        loc 되돌리기
        scroe 되돌리기
        depart[p] = false

 

4. 이미 누가 있는 칸인지 체크

 

loc : 0~3번 말의 현재 위치

alreadyFilled (현재 i, 현재 j)
	for (p: 0~3번 말)
		if 현재 i,j와 p번 말의 위치가 10 or 20 or 40
        	return true; // 겹치는 자리
        
        if i==0 // 빨강 경로면 그냥 i,j와 p 위치만 확인
        	if i,j == p번 말 위치
            	return true
        else // 현재 옮기려는 위치가 경로1~3위에 있으며, 겹치는 구간인 25 30 35 40에 있음
        	if i,j와 tmp가 25 35 40이면 // 25 35 40은 하나만 존재, 같다면 위치가 겹치는 것
            	return true
            else if i,j와 tmp가 30일 때 // 30은 경로3,0과 공통경로 30 두 군데에 존재, 구분해야 함
            	if i,j가 3,0일 때
                	tmp도 3,0 일 때
                		return true // 겹침
                else // i, j는 3,0이 아님, 공통 경로에 있음 -> p도 3,0이 아니면 겹침
                	if p가 3,0이 아니면
                    	return true
    return false

 

 

구현 코드

bool alreadyFilled(int i, int j) { // 해당 칸에 이미 자리가 있으면 true
    for (int p = 0; p < 4; p++) {
        int tmp = board[loc[p].first][loc[p].second];
        if (board[i][j] == 10 && tmp == 10)
            return true;
        if (board[i][j] == 20 && tmp == 20)
            return true;
        if (board[i][j] == 40 && tmp == 40)
            return true;
        if (i == 0) {
            if (i == loc[p].first && j == loc[p].second)
                return true;
        } else { // i가 1, 2, 3일 때, 25 30 35 40 이 겹침
            if (board[i][j] == 25 || board[i][j] == 35 || board[i][j] == 40) {
                if (tmp == board[i][j])
                    return true;
            } else if (board[i][j] == 30 && tmp == 30) {
                if (i == 3 && j == 0) {
                    if (loc[p].first == 3 && loc[p].second == 0)
                        return true;
                } else {                                              // 중간에 있는 30 일 때
                    if (!(loc[p].first == 3 && loc[p].second == 0)) { // 얘도 중간에 있는 거면
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

 

 

전체 코드

/*boj g2 17825 주사위 윷놀이*/
#include <iostream>
#include <tuple>
#include <vector>
#define MAXN 25
using namespace std;

int board[4][MAXN] = {
    {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0},
    {10, 13, 16, 19, 25, 30, 35, 40, 0},
    {20, 22, 24, 25, 30, 35, 40, 0},
    {30, 28, 27, 26, 25, 30, 35, 40, 0}}; // 빨강, 파10, 파20, 파30

int endIdx[4] = {21, 8, 7, 8};
int dice[10];
pair<int, int> loc[4]; // 0, 1, 2, 3번째 말의 위치
bool depart[4];        // 0 ~ 3번 말이 도착했는지

void input() {
    for (int i = 0; i < 10; i++)
        cin >> dice[i];
}

int score = 0;
int mx = -1;

vector<int> vec;

bool alreadyFilled(int i, int j) { // 해당 칸에 이미 자리가 있으면 true
    // if (board[i][j] != 0 && vis[board[i][j]])
    //     return true;
    // else
    //     return false;

    for (int p = 0; p < 4; p++) {
        int tmp = board[loc[p].first][loc[p].second];
        if (board[i][j] == 10 && tmp == 10)
            return true;
        if (board[i][j] == 20 && tmp == 20)
            return true;
        if (board[i][j] == 40 && tmp == 40)
            return true;
        if (i == 0) {
            if (i == loc[p].first && j == loc[p].second)
                return true;
        } else { // i가 1, 2, 3일 때, 25 30 35 40 이 겹침
            if (board[i][j] == 25 || board[i][j] == 35 || board[i][j] == 40) {
                if (tmp == board[i][j])
                    return true;
            } else if (board[i][j] == 30 && tmp == 30) {
                if (i == 3 && j == 0) {
                    if (loc[p].first == 3 && loc[p].second == 0)
                        return true;
                } else {                                              // 중간에 있는 30 일 때
                    if (!(loc[p].first == 3 && loc[p].second == 0)) { // 얘도 중간에 있는 거면
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

bool notDepart(int i, int j) { // i, j가 도착점이라면 false, 도착점이 아니면 true
    if (endIdx[i] == j)
        return false;
    return true;
}

pair<int, int> move(int i, int j, int d) {
    if (j + d >= endIdx[i]) // 도착 지점에 도착
        return make_pair(i, endIdx[i]);

    int nj = j + d;

    if (i == 0 && nj == 5) {
        return make_pair(1, 0);
    } else if (i == 0 && nj == 10) {
        return make_pair(2, 0);
    } else if (i == 0 && nj == 15) {
        return make_pair(3, 0);
    }

    return make_pair(i, nj);
}

void printVec() {
    cout << "\n=====vec=====\n";
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }
    cout << "\n";
}

void dfs(int k) { // 0~9번째 dice
    if (k == 10) {
        mx = max(mx, score);
        // if (score == 190 || score == 193) {
        //     printVec();
        //     cout << score << "\n";
        // }
        return;
    }

    for (int p = 0; p < 4; p++) {
        if (depart[p]) continue;
        int i = loc[p].first;
        int j = loc[p].second;
        int ni, nj;
        tie(ni, nj) = move(i, j, dice[k]);

        if (alreadyFilled(ni, nj) && notDepart(ni, nj))
            continue;

        if (!notDepart(ni, nj)) {
            depart[p] = true;
        }

        loc[p].first = ni;
        loc[p].second = nj;
        score += board[ni][nj];
        vec.push_back(p);

        dfs(k + 1);

        vec.pop_back();
        loc[p].first = i;
        loc[p].second = j;
        score -= board[ni][nj];
        depart[p] = false;
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();

    dfs(0);

    cout << mx << '\n';
}