[BOJ] 백준 1079 마피아

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

 Input 

4

500 500 500 500

1 4 3 -2

-2 1 4 3

3 -2 1 4

4 3 -2 1

1

 

 Output 

2

 

마피아는 1명만 있다고 보면 됩니다. 왜냐하면 "은진이는 마지막 남은 마피아"이기 때문입니다.

그리고 그 마피아가 오래 살아남을 수 있는 경우를 구하는 문제입니다.

(정답은 마피아 밤을 가진 횟수)

[낮]

- 살아남은 player 수 = 홀수

- 유죄지수가 가장 높은 사람을 죽인다,

  유지지수가 같으면 플레이어 번호가 낮은 사람을 죽인다.

[밤]

- 살아남은 player 수 = 짝수

- 마피아가 죽일 사람을 한 명 고른다.

  마피아 자기자신과 죽은사람을 제외한 모든 Case를 DFS 탐색

- 죽이고나서는 유죄지수를 갱신

 

[게임 종료 조건]

- 플레이어가 1명 남았을 때,

  마피아 게임 규칙상 플레이어가 2명 살아있는 경우는 시민 + 마피아 각 1명씩 있는 Case로

  바로 밤이 되어 마피아가 남은 시민을 죽일 수 있는 상황입니다.

  즉, 마피아 본인이 혼자 남은 Case로 이 경우가 가장 많은 밤을 보낸것을 의미합니다.

  문제에서 시간제한이 있기 때문에 이 경우를 찾으면 다른 무의미한 탐색을 종료시켜야 합니다.

- 마피아가 죽은 경우

  Player가 몇명 남았든 마지막 마피아가 죽은 것이므로 게임을 종료합니다.

---

#include <iostream>
using namespace std;
typedef struct {
    int point;
    bool isDead;
}player;
 
int N, mafia, answer = 0;
bool flag;
player players[16];
int R[16][16];
 
// 현재 남은 인원, 보냈던 밤의 횟수
void game(int playerCnt, int round) {
    if (flag) return;
 
    // 마피아가 죽었거나 마지막까지 살아남았거나
    if (players[mafia].isDead || playerCnt == 1) {
        answer = answer < round ? round : answer;
        if (playerCnt == 1) flag = true;
        return;
    }
 
    if (playerCnt % 2) { // 낮
        int target = 0;
        int maxPoint = 0;
        for (int i = 0; i < N; i++) {
            // 이미 죽은 사람인 경우
            if (players[i].isDead)
                continue;
            if (players[i].point > maxPoint) {
                target = i;
                maxPoint = players[i].point;
            }
        }
 
        players[target].isDead = true;
        game(playerCnt - 1, round);
        players[target].isDead = false;
    }
        
    else { // 밤
        for (int i = 0; i < N; i++) {
            // 이미 죽었거나 마피아 본인인 경우
            if (players[i].isDead || i == mafia) continue;
 
            // 유죄지수 갱신
            for (int j = 0; j < N; j++)
                players[j].point = players[j].point + R[i][j];
            players[i].isDead = true;
 
            game(playerCnt - 1, round + 1);
 
            // 유죄지수 원복
            for (int j = 0; j < N; j++)
                players[j].point = players[j].point - R[i][j];
            players[i].isDead = false;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> players[i].point;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> R[i][j];
    
    cin >> mafia;
 
    game(N, 0);
 
    cout << answer << endl;
    return 0;
}