[백준 1079] 마피아(JAVA)

링크

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

문제 설명

규칙

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

진행 방식

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

문제 풀이

문제에 나와있는 규칙을 그대로 적용시키면 간단하게 해결되는 문제였다.

소스코드

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

public class Baek_1079_마피아 {
	static int N, enjin, ans = 0;
	static int[] guilty;
	static int[][] R;
	static boolean[] isLive;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		guilty = new int[N];
		R = new int[N][N];
		isLive = new boolean[N];
		
		Arrays.fill(isLive, true);
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			guilty[i] = Integer.parseInt(st.nextToken());
		}
		
		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());
			}
		}
		
		enjin = Integer.parseInt(br.readLine());
		play(N, 0);
		System.out.println(ans);
	}

	static void play(int cnt, int day) {
		if(!isLive[enjin] || cnt == 1) {
			ans = Math.max(ans, day);
			return;
		}
		//짝수(밤)일 경우 랜덤으로 한명을 죽이다.
		if(cnt %2 == 0) {
			for(int i = 0; i < N; i++) {
				if(!isLive[i] || i == enjin)
					continue; 
				
				//guilty 바꾸기
				for(int j = 0; j < N; j++) {
					if(!isLive[j])
						continue;
					guilty[j] += R[i][j];
				}
				
				isLive[i] = false;
				play(cnt-1, day+1);
				isLive[i] = true;
				
				//guilty 복구
				for(int j = 0; j < N; j++) {
					if(!isLive[j])
						continue;
					guilty[j] -= R[i][j];
				}
			}
		}else {
			int max = 0, idx = N-1;
			
			for(int i = 0; i < N; i++) {
				if(isLive[i] && max < guilty[i]) {
					max = guilty[i];
					idx = i;
				}else if(isLive[i] && max == guilty[i]) {
					max = guilty[i];
					idx = Math.min(i, idx);
				}
			}
			
			isLive[idx] = false;
			play(cnt-1, day);
			isLive[idx] = true;
		}
	}
}

GITHUB

https://github.com/hoonze/SSAFY_Algorithm_Study/tree/master/SSAFYT_Study/etc/2021.12/Baek_1079_%EB%A7%88%ED%94%BC%EC%95%84