[BaekJoon] 1079 마피아 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int answer;
    static int N;
    static int[] guiltyScores; // 각 참가자의 유죄 지수
    static int[][] R; // 참가자 간의 반응을 나타내는 2차원 배열
    static int ej; // 은진의 참가자 번호
    static boolean[] isDeleted; // 각 참가자가 죽었는지에 대한 여부

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        answer = Integer.MIN_VALUE;
        guiltyScores = new int[N];
        R = new int[N][N];
        isDeleted = new boolean[N];

        for(int idx = 0; idx < N; idx++) {
            guiltyScores[idx] = scanner.nextInt();
        }

        for(int row = 0; row < N; row++) {
            for(int col = 0; col < N; col++) {
                R[row][col] = scanner.nextInt();
            }
        }

        ej = scanner.nextInt();
    }

    static void solution() {
        doMafiaGame(N, 0);
        System.out.println(answer);
    }

    // 재귀를 통해 밤에 죽이는 참가자의 여러 순서들을 모두 진행해보고
    // 은진이 죽는 경우나 은진이 마지막까지 남는 경우가 되었을 때까지 지난 밤의 수 중 가장 큰 수를 구한다
    static void doMafiaGame(int participantNum, int nightNum) {
        // 은진이 죽는 경우나 은진이 마지막까지 남는 경우라면
        if((participantNum == 1 && !isDeleted[ej]) || isDeleted[ej]) {
            // 지난 밤의 수 중 가장 큰 수로 answer 값을 갱신한다
            answer = Math.max(answer, nightNum);
            return;
        }

        if(participantNum % 2 == 1) { // 참가자 수가 홀수라면, 즉 낮이라면
            // 아직 죽지 않은 참가자 중 가장 유죄 지수가 높은 참가자를 구한다
            int maxParticipant = afternoonTurn();
            // 해당 참가자를 죽이고 게임의 다음 턴을 진행한다
            // 게임을 진행한 이후에는 다시 isDeleted 값을 false로 변경하여 다른 순서로 죽였을 때의 경우를 진행한다
            isDeleted[maxParticipant] = true;
            doMafiaGame(participantNum - 1, nightNum);
            isDeleted[maxParticipant] = false;
        } else { // 참가자 수가 짝수라면, 즉 밤이라면
            // 모든 참가자를 돌면서 죽일 참가자를 골라 게임을 진행한다
            for(int idx = 0; idx < N; idx++) {
                // 이미 죽은 참가자라면 다음 참가자를 확인한다
                if(isDeleted[idx])
                    continue;

                // 현재 참가자를 죽였을 때의 모든 참가자의 유죄 지수를 계산하고 현재 참가자를 죽인 후 다음 턴을 진행한다
                changeGuiltyScores(idx, true);
                isDeleted[idx] = true;
                doMafiaGame(participantNum - 1, nightNum + 1);
                // 다시 모든 참가자의 유죄 지수를 원래대로 돌리고 isDeleted 값도 false로 변경하여 다른 참가자를 죽였을 때의 경우를 진행해본다
                changeGuiltyScores(idx, false);
                isDeleted[idx] = false;
            }
        }
    }

    static int afternoonTurn() {
        int maxGuiltyScore = Integer.MIN_VALUE;
        int maxParticipant = -1;
        for(int idx = 0; idx < N; idx++) {
            if(isDeleted[idx])
                continue;

            // 유죄 지수가 가장 높은 참가자 중 가장 번호가 작은 참가자를 찾는다
            if(maxGuiltyScore < guiltyScores[idx]) {
                maxGuiltyScore = guiltyScores[idx];
                maxParticipant = idx;
            }
        }

        // 가장 유죄 지수가 높은 참가자 중 가장 번호가 작은 참가자의 번호를 반환한다
        return maxParticipant;
    }

    static void changeGuiltyScores(int deletedParticipant, boolean isPlus) {
        // 모든 참가자를 순회하면서 유죄 지수를 갱신한다
        for(int idx = 0; idx < N; idx++) {
            // 이미 죽은 참가자이거나 현재 참가자가 이번 턴에 죽일 참가자일 경우 다음 참가자를 확인한다
            if(isDeleted[idx] || idx == deletedParticipant)
                continue;

            // 유죄 지수를 갱신한다
            if(isPlus)
                guiltyScores[idx] += R[deletedParticipant][idx];
            else
                guiltyScores[idx] -= R[deletedParticipant][idx];
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}