백준 / 1079 / 마피아 / C++

문제 링크 : https://www.acmicpc.net/problem/1079

#include <bits/stdc++.h>

using namespace std;

int n;
int mafia;
int ans = 0;
vector<bool> alive;
vector<int> guiltyrate;
vector<vector<int>> R;

void func( int alivecount, int nightcount, int turn)
{
    if (alivecount == 1)
    {
        ans = max(ans, nightcount);
        return;
    }
    if (turn == 1) // 마피아 턴
    {
        for (int i = 0; i < n; i++) // 죽일사람 선택
        {
            if (!alive[i] || i == mafia)
            {
                continue;
            }
            alive[i] = false; // i를 선택해서 죽임
            for (int j = 0; j < n; j++)
            {
                if (j == i)
                {
                    continue;
                }
                guiltyrate[j] += R[i][j];
            }
            func(alivecount - 1, nightcount + 1, turn * -1);
            alive[i] = true;
            for (int j = 0; j < n; j++)
            {
                if (j == i)
                {
                    continue;
                }
                guiltyrate[j] -= R[i][j];
            }
        }
    }
    else // 시민 턴
    {
        int maxguiltyval = 0;
        int deathidx;
        for (int i = 0; i < n; i++)
        {
            if (!alive[i])
            {
                continue;
            }
            if (maxguiltyval < guiltyrate[i])
            {
                maxguiltyval = guiltyrate[i];
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (!alive[i])
            {
                continue;
            }
            if (maxguiltyval == guiltyrate[i])
            {
                alive[i] = false;
                if (i == mafia)
                {
                    ans = max(ans, nightcount);
                    alive[i] = true;
                    return;
                }
                deathidx = i;
                break;
            }
        }
        func(alivecount - 1, nightcount, turn * -1);
        alive[deathidx] = true;
    }
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    cin >> n;
    alive.resize(n, true);
    guiltyrate.resize(n);
    R.resize(n, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        cin >> guiltyrate[i];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> R[i][j];
        }
    }
    cin >> mafia;
    if (n % 2 == 0)
    {
        func(n, 0, 1);
    }
    else
    {
        func(n, 0, -1);
    }
    cout << ans;
    return 0;
}

구현 문제다. 문제 호흡이 길기 때문에 각 턴에서 어떤 상황이 일어나는지, 그리고 어떤 것을 갱신해서 답을 구해야 하는지부터 살펴보았다.

우선 참가자(생존자)의 짝/홀수 여부로 낮/밤이 결정되고, 각 낮/밤에는 일어나는 일이 달라진다. 그것에 중점을 둬서 turn 변수를 통해 낮/밤을 결정지었고, 낮에는 유죄 지수가 가장 높은 인원들 중 번호가 가장 낮은 인원을 죽이고, 밤에는 마피아가 죽일 사람을 결정한 뒤, 그 인덱스에 알맞게 유죄 지수를 갱신하는 과정을 작성했다.

원래는 모든 배열을 지역변수로 선언한 뒤 함수에 파라미터로 전달했는데, 시간 초과가 났다. 그래서 모든 배열을 전역변수로 선언한 뒤 alive를 true와 false로 변환하는 과정을 추가했고, 시간 초과를 해결해서 AC를 받았다.