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

백준의 마피아(1079) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 마피아 게임을 하면서 게임을 가장 오래할 수 있는 방법을 찾는 문제이다.

   먼저, 본인은 사람에 대한 각각의 정보를 저장할 수 있는 구조체를 하나 선언해 주었다.

   구조체에서는 2개의 멤버변수를 관리한다. 하나는 해당 사람의 점수(int) , 또 하나는 생존여부(bool) !

   위의 구조체를 배열로 만들어서 선언 후, 초기 생존여부는 모두 true, 즉 모두 살아있는 것으로 체크해 주었다.

 

   이제 본격적인 마피아 게임으로 들어가보자.

   본인은 깊이우선탐색(DFS)로 게임을 진행해 보았다. 매개변수로는 ( 현재남은 인원 , 지난 밤의 횟수 ) 를 호출해 주었다.

   먼저, 밤일 경우부터 차근차근 알아보자. 밤은 남은 사람이 짝수일 경우, 즉, 매개변수로 호출된 '현재남은 인원' % 2 한

   값이 0일 경우 진행된다.

   밤에 해야할 일에서 본인이 가장 먼저 생각한 것은 순열을 구현하는 것이였다. 밤에는 은진이(마피아)가 한 명을 죽일 수

   있는데, 누구를 죽이는지에 따라서 점수가 달라질 것이고, 이러한 변화 때문에 게임을 얼마나 길게할 수 있는지가

   달라지게 된다. 즉, 남아 있는 사람들을 어떤 순서로 죽일지 발생할 수 있는 모든 경우의 수를 탐색해 보면서 게임을

   진행하는 것이다. 아직 순열을 구하는 법을 모른다면 아래의 글을 읽고 오도록 하자.

   [ 순열 구현하기(Click) ]

  

   낮에는, 유죄점수가 가장 높은 사람을 죽인다.

   이 부분은 단순 for문을 통해서 유죄점수가 가장 높은 사람을 찾아주었다.

   게임을 종료하기 위한 조건은 2가지가 있다.

   1. 플레이어가 1명이 남았을 때

   - 플레이어가 1명이 남게 되면 시민이든 마피아든 어느 한쪽이 승리하고 게임이 끝날 것이다.

   2. 은진이가 죽었을 때

   - 은진이가 죽게 되면, 플레이어가 몇 명이 남든 게임이 끝나게 된다. 왜냐하면 은진이는 "마지막 남은 마피아" 이기

     때문에, 은진이가 죽는다는 것은, 곧 시민의 승리로 게임이 끝나게 된다는 것이다.

  

   처음에는 단순히 위의 2가지 경우를 종료조건문으로 걸어주고, 낮과 밤을 모두 백트래킹으로 구현을 했는데, 시간초과가

   발생했다. 그래서 시간을 줄이기 위해서 여러가지 조건을 생각해보다가 한 부분을 더 추가해 줬더니 pass를 받았다.

   바로, "플레이어가 1명 남았을 때, 그게 은진이일 경우"

   이 경우를 생각해보자. 1명이 남았는데 그게 은진이다 라는 것은 결국 마피아의 승리로 끝났다는 것은 물론,

   이 케이스보다 은진이가 게임을 더 오래할 수 있는 경우가 존재할까 ??

   절대 존재하지 않는다. 은진이가 마지막까지 살아남았는데 어떻게 게임을 더 진행할 수 있을까 ??

   따라서, 플레이어가 1명 남았고, 은진이가 살아있다면 그 경우보다 더 길게 게임을 할 수 있는 경우는 없으므로

   이 조건문에 걸리게 되면 백트래킹에 의해서 재귀함수가 다시 빠지게 되더라도 더 이상의 탐색같은 것은 하지 않도록

   만들어 주었다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
struct INFO
{
    int Score;
    bool LIVE;
};
 
bool Flag;
int N, Mafia_Idx, Answer;
int Score_Board[MAX][MAX];
INFO Player[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Player[i].Score;
        Player[i].LIVE = true;
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> Score_Board[i][j];
        }
    }
    cin >> Mafia_Idx;
}
 
void DFS(int PN, int Day)
{
    if (Flag == true) return;
    if (Player[Mafia_Idx].LIVE == false || PN == 1)
    {
        Answer = Bigger(Answer, Day);
        if (PN == 1 && Player[Mafia_Idx].LIVE == true) Flag = true;
        return;
    }
    
    if (PN % 2 == 0)
    {
        for (int i = 0; i < N; i++)
        {
            if (i == Mafia_Idx) continue;
            if (Player[i].LIVE == false) continue;
 
            Player[i].LIVE = false;
            for (int j = 0; j < N; j++)
            {
                if (Player[j].LIVE == false) continue;
                Player[j].Score = Player[j].Score + Score_Board[i][j];
            }
            DFS(PN - 1, Day + 1);
            if (Flag == true) return;
 
            for (int j = 0; j < N; j++)
            {
                if (Player[j].LIVE == false) continue;
                Player[j].Score = Player[j].Score - Score_Board[i][j];
            }
            Player[i].LIVE = true;
        }
    }
    else
    {
        int Max_Score = 0;
        int Idx = 0;
        for (int i = 0; i < N; i++)
        {
            if (Player[i].LIVE == false) continue;
            
            if (Player[i].Score > Max_Score)
            {
                Max_Score = Player[i].Score;
                Idx = i;
            }
            else if (Player[i].Score == Max_Score) Idx = Min(Idx, i);
        }
 
        Player[Idx].LIVE = false;
        DFS(PN - 1, Day);
        if (Flag == true) return;
        Player[Idx].LIVE = true;
    }
}
 
void Solution()
{
    DFS(N, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}