[BOJ] 백준 1079 : 마피아 (java)

🧪 1079 마피아

---

난이도 : 🌟 골드 2
유형 : 브루트포스

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

 

📝 문제

---

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

 

1. 참가자는 두 그룹으로 나누어진다. 한 그룹은 마피아이고, 또 다른 그룹은 선량한 시민이다. 마피아의 정체는 시민에게 알려져 있지 않다. 참가자의 번호는 0번부터 시작한다.

2. 참가자가 짝수 명 남았을 때는 밤이다. 밤에는 마피아가 죽일 사람 한 명을 고른다. 죽은 사람은 게임에 더 이상 참여할 수 없다.

3. 참가자가 홀수 명 남았을 때는 낮이다. 낮에는 참가자들이 가장 죄가 있을 것 같은 사람 한 명을 죽인다.

4. 만약 게임에 마피아가 한 명도 안 남았다면, 그 게임은 시민 팀이 이긴 것이고, 시민이 한 명도 안 남았다면, 그 게임은 마피아 팀이 이긴 것이다. 게임은 즉시 종료된다.

 

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

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

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

 

1. 밤에는 마피아가 죽일 사람을 한 명 고른다. 이 경우 각 사람의 유죄 지수가 바뀐다. 만약 참가자 i가 죽었다면, 다른 참가자 j의 유죄 지수는 R[i][j]만큼 변한다.

2. 낮에는 현재 게임에 남아있는 사람 중에 유죄 지수가 가장 높은 사람을 죽인다. 그런 사람이 여러 명일 경우 그중 번호가 가장 작은 사람이 죽는다. 이 경우 유죄 지수는 바뀌지 않는다.

 

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

 

 

입력

 

첫째 줄에 참가자의 수 N이 주어진다. 둘째 줄에는 각 참가자의 유죄 지수가 주어진다. 셋째 줄부터 N개의 줄에는 배열 R이 주어진다. 마지막 줄에는 은진이의 참가자 번호가 주어진다. N은 16보다 작거나 같은 자연수이고, 유죄 지수는 300보다 크거나 같고, 800보다 작거나 같은 자연수이다. R배열에 있는 수는 모두 절댓값이 1보다 크거나 같고 26보다 작거나 같은 정수이다.

 

출력

 

첫째 줄에 문제의 정답을 출력한다.

 

🧐 핵심 로직

---

1. 게임에 참여하는 모든 사람의 수 n만큼 guilty 배열과 isDead 배열을 만들어 각 참가자의 유죄 지수와 생존 여부를 관리한다.

 

2. 참가자 간의 반응을 나타내는 2차원 배열 R을 입력받아 저장한다.

 

3. 은진이(마지막 마피아)의 번호를 number 변수에 저장한다.

 

4. DFS를 사용하여 게임의 모든 가능한 상황을 탐색한다:

    4 - a) 밤일 때(참가자가 짝수 명 남았을 때):

        4 - a - 1) 은진이를 제외한 모든 살아있는 참가자를 한 명씩 죽이는 경우를 시도한다.

        4 - a - 2) 참가자를 죽일 때마다 resizeGuilty 함수를 사용하여 참가자가 죽었을 때 다른 참가자들의 유죄 지수를 조정한다.

 

    4 - b) 낮일 때(참가자가 홀수 명 남았을 때):

        4 - b - 1) 유죄 지수가 가장 높은 살아있는 참가자를 찾아 죽인다.

 

5. 게임 종료 조건(은진이가 죽거나 1명만 남았을 때)에 도달하면, 진행된 밤의 횟수를 res와 비교하여 최대값을 저장한다.

 

6. 모든 가능한 경우를 탐색한 후, 최대 진행 가능한 밤의 횟수 res를 출력한다.

 

💻 최종 코드 (560 ms)

---

import java.util.*;
import java.io.*;

public class Main {

    static int n, number, res;
    static int[] guilty;
    static boolean[] isDead;
    static int[][] R;
    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        n = Integer.parseInt(br.readLine());

        guilty = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            guilty[i] = Integer.parseInt(st.nextToken());
        }

        R = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                R[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        isDead = new boolean[n];
        number = Integer.parseInt(br.readLine());

        int len = guilty.length;

        dfs(len, 0);

        System.out.println(res);

        br.close();
    }

    private static void dfs(int len, int cnt) {

        if (isDead[number] || len == 1) {
            res = Math.max(res, cnt);
            return;
        }

        if (len % 2 == 0) {
            for (int i = 0; i < n; i++) {
                if (!isDead[i] && i != number) {
                    isDead[i] = true;
                    resizeGuilty(0, i);
                    dfs(len - 1, cnt + 1);
                    resizeGuilty(1, i);
                    isDead[i] = false;
                }
            }
        } else {
            int maxGuilty = Integer.MIN_VALUE;
            int idx = 0;

            for (int i = 0; i < n; i++) {
                if (!isDead[i] && maxGuilty < guilty[i]) {
                    maxGuilty = guilty[i];
                    idx = i;
                }
            }

            isDead[idx] = true;
            dfs(len - 1, cnt);
            isDead[idx] = false;
        }
    }

    private static void resizeGuilty(int type, int idx) {

        if (type == 0) {
            for (int i = 0; i < n; i++) {
                if (!isDead[i]) {
                    guilty[i] += R[idx][i];
                }
            }
        } else {
            for (int i = 0; i < n; i++) {
                if (!isDead[i]) {
                    guilty[i] -= R[idx][i];
                }
            }
        }
    }
}