[ 백준 BOJ ] 1079번 - 마피아 (C++)

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

 

생각 흐름

• N이 짝수로 주어졌을 때의 밤도 카운팅해야 되는지 예제로 확인.
• N의 최댓값은 16이고, dfs로 죽이거나 안 죽이거나를 따졌을 때 2^16으로 6만 정도임을 확인
• dfs는 무조건 밤인 상황으로 만들기 위해 한 dfs 실행 시에 내부적으로 죽일 애를 정하고, 죽인 애에 대해 유죄 지수를 계산해준 다음 낮에 죽이는 애까지 결정해주었다.
• 그렇게 N에 대해 2중 for문이 생겨 최종 시간 복잡도는 16*16*2^16으로 1600만이다.
• 성공

 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int N;
vector<vector<int>> vv;
int mafia;
int answer;
int guilt[16];

void dfs(int night){
    
    if(guilt[mafia]==-1){
        return;
    }
    
    int count = 0;
    for(int i = 0; i<N; i++){
        if(guilt[i]!=-1){
            count++;
        }
    }
    if(count==1){
        return;
    }
    
    answer = max(answer, night);
    
    for(int i = 0; i<N; i++){
        if(i == mafia) continue;
        if(guilt[i]!=-1){
            int tmp1 = guilt[i];
            guilt[i]=-1;
            int maxNum = -1;
            int num = -1;
            
            for(int j = 0; j<N; j++){
                if(guilt[j]==-1) continue;
                guilt[j]+=vv[i][j];
                if(maxNum<guilt[j]){
                    maxNum = guilt[j];
                    num = j;
                }
            }
            int tmp2 = guilt[num];
            guilt[num] = -1;

            dfs(night+1);

            guilt[num] = tmp2;
            
            for(int j = 0; j<N; j++){
                if(guilt[j]==-1) continue;
                guilt[j]-=vv[i][j];
            }
            
            guilt[i]=tmp1;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N;
    
    for(int i = 0; i<N; i++){
        int tmp;
        cin>>tmp;
        
        guilt[i] = tmp;
    }
    
    for(int i = 0; i<N; i++){
        vector<int> v;
        
        for(int j = 0; j<N; j++){
            int tmp;
            cin>>tmp;
            
            v.push_back(tmp);
        }
        vv.push_back(v);
    }
    
    cin>>mafia;
    
    if(N%2==0){
        dfs(1);
    }else{
        int maxNum = -1;
        int num = -1;
        for(int i = 0; i<N; i++){
            if(maxNum<guilt[i]){
                maxNum = guilt[i];
                num = i;
            }
        }
        guilt[num]=-1;
        dfs(1);
    }
    
    cout<<answer<<endl;
    
    return 0;
}