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

[문제보기]

 

[해결과정]

 1. 총 4가지 입력 (1. 사람 수, 2. 사람 마다 각각의 점수, 3. 2차원 배열의 점수표, 4. 은진이 IDX)

 

 2. DFS (브루트포스)

  2-1. 기저조건 : 은진이가 죽거나, 남은 사람이 1명 일 때...

 

  2-2. 현재 인원이 짝수일 경우 (밤)

   2-2-1. 사람 수 만큼 for문을 돌며, 은진이거나 이미 죽은 사람 인덱스라면 continue;

   2-2-2. 그렇지 않으면 해당 인덱스 사람을 죽이고, 나머지 살아있는 사람들의 점수를 변경

   2-2-3. DFS 실행 (사람-1, 날짜+1)

   2-2-4. 시행 후 위 과정을 반대로 시행

 

  2-3. 현재 인원이 홀수일 경우 (낮)

   2-3-1. 점수가 가장 높은 사람 찾기

   2-3-2. 은진이가 가장 점수가 높을 경우 기저조건 시행

   2-3-3. 그렇지 않으면 점수가 가장 높은 사람 죽이고 DFS 실행 (사람-1, 날짜는 그대로)

   2-3-4. 시행 후 2-3-3을 반대로 진행

 

[소스코드]

#include<iostream>
#include<memory.h>
#include<vector>
using namespace std;
const int MAX = 18;
 
int n;
int score[MAX];
int check[MAX];
int arr[MAX][MAX];
int en;
 
int ans = 0;
 
int findKill() {
    int maximum = 0;
    int idx;
    for (int i = 0; i < n; i++) {
        if (score[i] > maximum && check[i]==0) {
            maximum = score[i];
            idx = i;
        }
    }
    return idx;
}
 
void dfs(int man, int day) {
    if (check[en] == 1 || man == 1) {
        if (day > ans) ans = day;
        return;
    }
 
    //밤일경우
    if (man % 2 == 0) {
        for (int i = 0; i < n; i++) {
            if (i == en || check[i] == 1) continue;
 
            check[i] = 1;
            for (int j = 0; j < n; j++) {
                if(check[j]==0) score[j] += arr[i][j];
            }
            dfs(man - 1, day + 1);
 
            for (int j = 0; j < n; j++) {
                if (check[j] == 0) score[j] -= arr[i][j];
            }
            check[i] = 0;
            
        }
    }
    //낮일경우
    else {
        // 점수가 가장 높은 사람 죽이기.
        int kill = findKill();
        if (kill == en) {
            if (day > ans) ans = day;
            return;
        }
        check[kill] = 1;
        dfs(man - 1, day);
        check[kill] = 0;
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> score[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    cin >> en;
 
    dfs(n, 0);
 
    cout << ans << "\n";
 
 
    return 0;
}

 

[해결 과정 중 실수한 부분]

 1. 단순 완전탐색 문제였다. 사실 '마피아 게임'을 잘 몰라서 내용을 이해하는데 어려움이 있었다.

 2. 은진이를 무조건 살리는 방향으로 게임을 진행했다. 그러다 보니, 중간에 꼬이는 부분이 있어 계속 시간초과가 발생했다. 무려 4번의 '시간초과'를 보고 잘못된 부분을 찾았다... 그냥 은진이를 죽여도 됐다...

 

[관련 문제 혹은 비슷한 문제]

 완전탐색 문제