[프로그래머스] 주사위 고르기 (c++) 조합

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/258709

프로그래머스

풀이 방법

각 모든 경우의 수의 조합을 다 구하면 된다.

그러기 위해 dfs를 활용하여 백트레킹을 이용해 구현했다.

만약 선택한 수가 cnt라면 가능한 승리 횟수를 구했는데

여기서 visited 배열은 A가 선택한 주사위이다. 

A의 주사위만 선택하고 B의 주사위는 visited의 인덱스가 0인 것만 추가해 줬다.
주사위를 다 선택하면 A와 B가 만들 수 있는 수를 구해야 한다. 
이를 위해 또 dfs를 활용했다. 모든 가능한 수를 구해 벡터에 저장하고, 이를 비교하며 승리하는 경우의 수를 구했다.

그리고 이길 확률은 이긴 승리만횟수만 저장하면 된다. (어차피 게임 횟수는 모두 동일하기 때문)

 

#include <string>
#include <vector>
#include <memory.h>
#include <iostream>

using namespace std;

vector<vector<int>> gdice;
vector<int> answer;
int ans_win = 0;
vector<int> a_dice, a_val;
vector<int> b_dice, b_val;
int visited[10];

void a_can_dfs(int idx, int cnt, int val) {
    int now_val = val + gdice[a_dice[cnt]][idx]; // 다음 주사위 값
    if (cnt == a_dice.size()-1) { //선택 다 한 경우
        a_val.push_back(now_val);
        return;
    }
    
    for (int i = 0;i < gdice[0].size();i++) {
        a_can_dfs(i, cnt+1, now_val);
    }
    return ;
}

void b_can_dfs(int idx, int cnt, int val) { //주사위 내의 인덱스, 주사위 수, 현재 값
    int now_val = val + gdice[b_dice[cnt]][idx];
    if (cnt == b_dice.size()-1) {
        b_val.push_back(now_val);
        return;
    }
    
    for (int i = 0;i < gdice[0].size();i++) {
        b_can_dfs(i, cnt+1, now_val);
    }
    return ;
}

void make_b_dice() { // a가 선택한 주사위인 visited를 제외한 주사위를 b에 넣음
    for (int i = 0;i < gdice.size();i++) {
        if (visited[i] == 0) {
            b_dice.push_back(i);
        }
    }
}

int cal_win() {   // 승리한 횟수 계산
    a_val.clear();
    b_val.clear();      
    make_b_dice(); // b 주사위 만듦
    for (int i = 0;i < gdice[0].size();i++) {
        a_can_dfs(i, 0, 0);
    }
    for (int i = 0;i < gdice[0].size();i++) {
        b_can_dfs(i, 0, 0);
    }    
    int win_cnt = 0, total_cnt = 0;
    for (int i = 0;i < a_val.size();i++) {
        for (int j = 0;j < b_val.size();j++) {
            if (a_val[i] > b_val[j]) {
                win_cnt++;
            }            
        }
    }
    return win_cnt;
}

void dfs(int idx, int cnt) { //주사위의 인덱스, 선택한 수   
    
    if (cnt == gdice.size() / 2) {                
        b_dice.clear();
        int win_num = cal_win();
        if (win_num > ans_win) { // 정답 갱신
            ans_win = win_num;
            answer = a_dice;
        }
    }
    for (int i = idx+1;i < gdice.size();i++) {
        visited[i] = 1;
        a_dice.push_back(i);
        dfs(i, cnt+1);
        visited[i] = 0; //백트레킹
        a_dice.pop_back();
    }
    
    return ;
}

vector<int> solution(vector<vector<int>> dice) {
            
    gdice = dice; 
    memset(visited, 0, sizeof(visited));
    for (int i = 0;i < gdice.size();i++) {
        visited[i] = 1;
        a_dice.push_back(i);
        dfs(i ,1);
        visited[i] = 0; //백 트레킹
        a_dice.pop_back();
    }
    for (int i = 0;i < answer.size();i++) {
        answer[i]++;
    }
    return answer;
}