[백준]#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

4
500 500 500 500
1 4 3 -2
-2 1 4 3
3 -2 1 4
4 3 -2 1
1

예제 출력 1

2

풀이

이 문제는 dfs(깊이 우선 탐색) 알고리즘을 이용해서 풀 수 있었다. 처음에 문제를 잘못 이해해서 여러 번 틀렸다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int N;
    static int ans = 0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] score = new int[N];             //유죄 지수를 저장하기 위한 배열
        for(int i=0; i<N; i++) {
            score[i] = Integer.parseInt(input[i]);
        }

        int[][] R = new int[N][N];            //유죄 지수를 바꿀 때 이용하는 값 저장
        for(int i=0; i<N; i++) {
            input = br.readLine().split(" ");

            for(int j=0; j<N; j++) {
                R[i][j] = Integer.parseInt(input[j]);
            }
        }

        int mafia = Integer.parseInt(br.readLine());

        dfs(0, mafia, N, R, score, new boolean[N]);

        System.out.println(ans);
    }

    public static void dfs(int time, int mafia, int cnt, int[][] R, int[] score, boolean[] visited) {
        if(cnt%2==1) {                //낮일 때
            int max = -1;
            int max_idx = -1;

            for(int i=0; i<N; i++) {
                if(!visited[i]) {
                    if(max < score[i]) {
                        max = score[i];
                        max_idx = i;
                    }
                }
            }

            if(max_idx==mafia) {            //마피아를 죽이면 시민 승으로 끝
                ans = Math.max(ans, time);
                return;
            }

            visited[max_idx] = true;

            dfs(time, mafia, cnt-1, R, score, visited);

            visited[max_idx] = false;
        }

        else {                  //밤일 때
            if(cnt==2) {                      //마피아 1명, 시민 1명이 남았으면 마피아 승으로 끝
                ans = Math.max(ans, time+1);
                return;
            }

            for(int i=0; i<N; i++) {
                if(i==mafia) continue;

                if(!visited[i]) {
                    visited[i] = true;

                    for(int j=0; j<N; j++) {        //유죄 지수 변경
                        score[j] += R[i][j];
                    }

                    dfs(time+1, mafia, cnt-1, R, score, visited);

                    for(int j=0; j<N; j++) {        //유죄 지수 회복
                        score[j] -= R[i][j];
                    }

                    visited[i] = false;
                }
            }
        }
    }
}