#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);
int rate[20][20];
bool live[20];
int criminal;
void DFS(int depth, int mode, int night)
{
if(depth == N) return;
if(mode == 1){
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;
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)
으로 바로 종료
해서 시간복잡도
를 굉장히 많이 줄일 수 있다는 것을 기억!