백준 1079 (마피아) - java

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

1079번: 마피아

백 트랙킹 문제이다. 주의해야 할 점은 낮과 밤에 따라 처리를 다르게 해주어야 한다는 것이다. 낮에는 점수 중 가장 높은 사람을 죽이고 밤에는 반복문을 통해 경우의 수를 계산한다. 그리고 낮에 만약 유진이가 죽었다면  버틴 밤의 횟수를 처리해주는 것도 생각해야 한다.

 

import java.io.*;
import java.util.*;
public class Main {
    static int n = 0;
    static int jin = 0;
    static int[] score = new int[17];
    static int[][] board = new int[17][17];

    static boolean[] visit = new boolean[17];

    static int re = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1;i<=n;i++)
        {
            score[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=1;i<=n;i++)
        {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=1;j<=n;j++)
            {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine(), " ");
        jin = Integer.parseInt(st.nextToken()) + 1; // 0부터 시작 ㅋㅋ

        int start = 0;
        if(n%2==0)
            start = 1;

        game(start,n,n%2);

        System.out.println(re);
        br.close();
    }
    // 낮 -> score[] 배열에서 점수가 가장 높은 사람을 죽여야 한다.
    static int day()
    {
        int idx = 0;
        int result = 0;
        for(int i=1;i<=n;i++)
        {
            if(!visit[i])
            {
                if(result < score[i])
                {
                    result = score[i];
                    idx =i;
                }
            }
        }

        return idx;
    }
    
    // cur -> 현재 몇번의 밤을 버텼는지 , rest -> 남은 인원 수, day -> 낮, 밤 구분
    static void game(int cur,int rest,int day)
    {
        // 밤에 모두 죽이고 유진이가 게임을 승리한 경우
        if(rest==1&&!visit[jin])
        {
            re = Math.max(re,cur);
            return;
        }
        
        // 낮에 투표로 유진이가 죽은 경우 , 낮-> 밤으로 갈때 cur +1 , 그렇기에 생각
        if(visit[jin])
        {
            re = Math.max(re,cur-1);
            return;
        }
        
        // 낮
        if(day==1)
        {
            int result = day();
            visit[result] = true;
            game(cur+1,rest-1,2);
            visit[result] = false;
        }
        
        // 밤
        else{
            for(int i=1;i<=n;i++)
            {
                if(i==jin)
                    continue;

                if(!visit[i])
                {
                    visit[i] = true;
                    scoreUp(i);
                    game(cur,rest-1,1);
                    visit[i] = false;
                    scoreDown(i);
                }
            }
        }

    }
    
    // 유죄 지수 증가
    static void scoreUp(int cur)
    {
        for(int i=1;i<=n;i++)
        {
            if(i==cur)
                continue;

            score[i] += board[cur][i];
        }
    }
    
    // 유죄 지수 감소
    static void scoreDown(int cur)
    {
        for(int i=1;i<=n;i++)
        {
            if(i==cur)
                continue;

            score[i] -= board[cur][i];
        }
    }
}