1079 마피아 (자바스크립트)

문제

은진이는 요즘 마피아라는 게임에 빠져 있다. 이 게임의 규칙은 다음과 같다.

1. 참가자는 두 그룹으로 나누어진다. 한 그룹은 마피아이고, 또 다른 그룹은 선량한 시민이다. 마피아의 정체는 시민에게 알려져 있지 않다. 참가자의 번호는 0번부터 시작한다.
2. 참가자가 짝수 명 남았을 때는 밤이다. 밤에는 마피아가 죽일 사람 한 명을 고른다. 죽은 사람은 게임에 더 이상 참여할 수 없다.
3. 참가자가 홀수 명 남았을 때는 낮이다. 낮에는 참가자들이 가장 죄가 있을 것 같은 사람 한 명을 죽인다.
4. 만약 게임에 마피아가 한 명도 안 남았다면, 그 게임은 시민 팀이 이긴 것이고, 시민이 한 명도 안 남았다면, 그 게임은 마피아 팀이 이긴 것이다. 게임은 즉시 종료된다.

게임을 잠시 동안 한 후에 은진이는 지금 이 게임에서 자기가 마지막으로 남은 마피아라는 것을 알았다. 따라서 은진이는 이 게임을 이기기 위해 방법을 생각하기 시작했다.

각 사람의 유죄 지수가 주어진다. 이 유죄 지수는 낮에 시민들이 어떤 참가자를 죽일 것인지 고를 때 쓰인다. 그리고 참가자 간의 반응을 나타내는 2차원 배열 R이 주어진다.

게임은 다음과 같이 진행된다.

1. 밤에는 마피아가 죽일 사람을 한 명 고른다. 이 경우 각 사람의 유죄 지수가 바뀐다. 만약 참가자 i가 죽었다면, 다른 참가자 j의 유죄 지수는 R[i][j]만큼 변한다.
2. 낮에는 현재 게임에 남아있는 사람 중에 유죄 지수가 가장 높은 사람을 죽인다. 그런 사람이 여러 명일 경우 그중 번호가 가장 작은 사람이 죽는다. 이 경우 유죄 지수는 바뀌지 않는다.

은진이는 되도록이면 이 게임을 오래 하고 싶다. 은진이가 이 게임에 정말 천재적으로 임하여 매번 최적의 선택을 할 때, 몇 번의 밤이 지나는지 출력하는 프로그램을 작성하시오.

 

=====

문제 풀이 

재귀로 유저의 인원 수가 짝수 홀수에 따라 밤과 낮의 행위를 해준다. 이 때 낮은 무조건 가장 높은 수만 죽이게 되므로 갈림길이 생기는 경우는 밤에 어떠한 사람을 죽일 지에 따라 달라진다. 

때문에 n 의 최댓값이 16이므로 가짓수가 생기는 것은 8! 이다. 8! 자체는 경우의 수가 적으므로 dfs방식으로 쭉 진행해도 시간 초과 걱정은 없다. 

주의할 점은 밤에 사람을 죽이고 유죄의 지수가 변할 때 gr[죽은 사람][다른 사람] 의 값으로 변하는게 아닌 그 값만큼 변하는 것이다.

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

let answer = 0;
const n = +input[0];
const guiltyNums = input[1].split(' ').map(Number);
const KILLED = -Infinity;

const gr = input.slice(2, 2 + n).map((s) => s.split(' ').map(Number));
const eunjinNum = +input.at(-1);

// 밤
const killUser = (guilty, killNumber) => {
    guilty[killNumber] = KILLED;
    for (let i = 0; i < n; i++) {
        if (guilty[i] === KILLED) continue;
        guilty[i] += gr[killNumber][i];
    }
    return guilty;
};

// 낮에 하는 행위. 젤 높은 놈 죽이기
const killHighest = (guilty) => {
    const max = Math.max(...guilty);
    const idx = guilty.findIndex((v) => v === max);
    guilty[idx] = KILLED;
    return guilty;
};

const dfs = (stage, guilty, userCount) => {
    if (guilty[eunjinNum] === KILLED || userCount <= 1) {
        answer = Math.max(answer, stage);
        return;
    }
    if (userCount % 2 === 0) {
    // 밤
        for (let i = 0; i < n; i++) {
            if (guilty[i] === KILLED) continue;
            const temp = [...guilty];
            killUser(temp, i);
            dfs(stage + 1, temp, userCount - 1);
        }
    } else {
    //낮
        killHighest(guilty);
        dfs(stage, guilty, userCount - 1);
    }
};

dfs(0, guiltyNums, n);
console.log(answer);