문제
N명이 마피아 게임을 할 때, 마피아인 은진이가 최대 며칠 밤을 살아남을 수 있는지 구하라. 밤에는 마피아가 한 명을 죽이고, 낮에는 유죄 지수가 가장 높은 사람이 처형된다.
입력
첫째 줄에 N, 둘째 줄에 유죄 지수, 이후 N줄에 영향 행렬 R, 마지막 줄에 은진이 번호가 주어진다.
출력
은진이가 살아남는 최대 밤 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 2 |
풀이
백트래킹으로 밤에 죽일 대상을 선택하며 모든 경우를 탐색한다.
- 인원이 짝수(밤)이면 마피아가 한 명을 선택하여 제거하고 유죄 지수를 갱신한다
- 인원이 홀수(낮)이면 유죄 지수 최대인 사람을 자동 처형한다
- 은진이가 죽거나 1명만 남으면 그때까지의 밤 수를 기록한다
- 백트래킹으로 모든 선택을 되돌리며 최대 밤 수를 갱신한다
핵심 아이디어: N이 최대 16이지만 밤마다 2명씩 줄어 실제 탐색 공간은 관리 가능하다.
코드
package day799;
import java.io.*;
import java.util.*;
public class Day769BOJ1079마피아 {
static int N, num, ans = 0;
static int[] guilty;
static int[][] R;
static boolean[] isLive;
public static void main(String[] args) throws Exception {
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());
}
}
num = Integer.parseInt(br.readLine());
dfs(N, 0);
System.out.println(ans);
}
static void dfs(int cnt, int day) {
if (!isLive[num] || cnt == 1) {
ans = Math.max(ans, day);
return;
}
if (cnt % 2 == 0) {
for (int i = 0; i < N; i++) {
if (!isLive[i] || i == num)
continue;
for (int j = 0; j < N; j++) {
if (!isLive[j])
continue;
guilty[j] += R[i][j];
}
isLive[i] = false;
dfs(cnt - 1, day + 1);
isLive[i] = true;
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;
dfs(cnt - 1, day);
isLive[idx] = true;
}
}
}복잡도
- 시간: O(N!)
- 공간: O(N)