마피아

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
int N, ans;
vector<int> guilty(20); // 0 ~ 최대 15까지 사용
int rate[20][20]; 
bool live[20];
int criminal;
// 15명에 대한 중복순열 --> 15! 
void DFS(int depth, int mode, int night)
{
    if(depth == N) return;
    /* 생존자 수가 홀수 -> 낮 */
    if(mode == 1){
        //int dead_C = max_element(guilty.begin(), guilty.end()) - guilty.begin();
        pair<int,int> M = {0,0};
        for(int a=0;a<N;a++)
        {
            if(!live[a]) continue;
            if(M.second < guilty[a]) M = {a, guilty[a]};
        }
        int dead_C = M.first;
        int save = guilty[dead_C];
        guilty[dead_C] = 0;
        live[dead_C] = false;
        if(dead_C == criminal) goto recovery;
        /* 여기까지 왔을 때 생존자 수가 1명이라면 마피아만 살아남은 것이니 최적의 경우니까 종료! */
        if(depth+1 ==  N-1){
            cout << night;
            exit(0);
        }
        ans = max(ans, night);
        DFS(depth+1, 0, night);
        recovery:;
        guilty[dead_C] = save;
        live[dead_C] = true;
    }else{
        /* 밤 */
        for(int i=0;i<N;i++)
        {
            if(i == criminal or !live[i]) continue;
            int dead_M = i;
            int tmp[20];
            for(int a=0;a<N;a++) tmp[a] = guilty[a];
            live[dead_M] = false;
            guilty[dead_M] = 0;
            for(int a=0;a<N;a++)
            {
                if(!live[a]) continue;
                guilty[a] += rate[dead_M][a];
            }
            ans = max(ans, night+1);
            DFS(depth+1, 1, night+1);
            live[dead_M] = true;
            for(int a=0;a<N;a++) guilty[a] = tmp[a];
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=0;i<N;i++)
        cin >> guilty[i];
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin >> rate[i][j];
    cin >> criminal;

    fill(live, live+20, true);
    if(N%2 == 0) DFS(0,0,0);
    else DFS(0,1,0);

    cout << ans;
    return 0;
}

• 로직
  • 백트래킹을 이용해서 밤에 마피아가 시민을 죽이는 모든 경우를 수행
  • 해당 과정에서 최적의 경우 (마피아가 마지막까지 살아남으면 더 이상의 최적 경우는 X)에 exit(0)

• 느낀 점
  • 최초 next_permutation()을 이용해서 모든 경우의 수에 대해 최대 night를 구함
    --> 총 15!이상의 매우매우 커다란 수가 된다
  • next_permutation()을 사용할 때 조합인지 / 순열인지 잘 파악하자 (중복 조합 / 순열)
  • 최적의 경우의 수가 있다면 exit(0)으로 바로 종료해서 시간복잡도를 굉장히 많이 줄일 수 있다는 것을 기억!