<Baekjoon> #1079 Brute Force_마피아 c++

#1079 마피아 참고1 참고2

Solution

• 은진이가 마지막으로 남은 마피아일 때 종료 조건은 1. 참가자가 1명이 남고 그 사람이 시민일 경우, 2. 참가자가 1명이 남고 그 사람이 은진이일 경우 이다
• 게임이 종료될 수 있을 때까지 모든 경우의 수를 따져보아야하는 Brute Force 문제
• 각 사람들의 유죄지수를 저장하는 배열, 생존 여부를 저장하는 배열 생성

DFS

• DFS 함수의 파라미터로는 현재 남은 player의 수 (pnum)과 몇 번의 밤이 지나갔는지 체크하는 (day)

• 기저조건은 참가자가 1명이 남았을 경우에 그 사람이 시민일 경우와 은진이일 경우로 나누어질 수 있다 (즉 은진이가 죽거나 남은 player가 1명일 경우로 표현 가능)

  if (pnum == 1 || alive[jin] == false) {
      if (day > ret) ret = day;
      return;
  }

• 밤 (pnum%2==0) : 마피아가 죽일 사람을 고름 (은진이는 죽을 수 없음)

1. 이미 죽었거나 은진이 외에 1명을 죽임
2. i를 죽였을 경우 다른 참가자 유죄지수를 R[i][] 만큼 변경해줌
3. dfs (pnum-1, day+1) : 사람을 1명 줄이고 밤을 추가해주어 dfs 호출
4. 변경해주었던 유죄지수를 다시 되돌려놓음
5. 죽인 i를 살림

	//night 
	if (pnum % 2 == 0) {
		for (int i = 0; i < N; i++) {
			if (alive[i] == false || i==jin) continue;

			alive[i] = false;
			for (int j = 0; j < N; j++) {
				if (alive[j] == false) continue;
				score[j] += guilty[i][j];
			}
				
			dfs(pnum - 1, day + 1);

			for (int j = 0; j < N; j++) {
				if (alive[j] == false) continue;
				score[j] -= guilty[i][j];
			}
			alive[i] = true;
		}
	}

• 낮 (pnum%2!=0) : 유죄지수가 가장 높은 사람을 죽임 (은진이가 죽을 수도 있음)

1. 유죄지수가 가장 높으면서 번호가 가장 작은 사람을 고름
2. 만약 이 사람이 은진이면 경기가 바로 끝나게 되므로 day의 최댓값을 갱신해주고 종료 (이 부분은 생략 가능)
3. 그렇지 않다면 이 사람을 죽임
4. dfs (pnum-1, day) : 사람을 1명 죽이지만 낮이므로 밤을 추가해주진 않음
5. 죽인 사람을 살림

	//day
	else {
		int max_score = 0;
		int kill=0;
		for (int i = 0; i < N; i++) {
			if (alive[i] == false) continue;
			if (max_score < score[i]) {
				max_score = score[i];
				kill = i;
			}
		}

		if (kill == jin) {
			if (ret < day) ret = day;
			return;
		}
		alive[kill] = false;
		dfs(pnum - 1, day);
		alive[kill] = true;
	}

Source Code

#include <iostream>
#include <vector>

const int MAX = 17;

using namespace std;

int ret=0;
int N;
int jin;
int score[MAX];
bool alive[MAX];
int guilty[MAX][MAX];

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> score[i];
		alive[i] = true;
	}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> guilty[i][j];
	cin >> jin;

}

void dfs(int pnum, int day) {
	//은진이가 죽거나 남아있는 player가 1명일 때
	if (pnum == 1 || alive[jin] == false) {
		if (day > ret) ret = day;
		return;
	}

	//night 
	if (pnum % 2 == 0) {
		for (int i = 0; i < N; i++) {
			if (alive[i] == false || i==jin) continue;

			alive[i] = false;
			for (int j = 0; j < N; j++) {
				if (alive[j] == false) continue;
				score[j] += guilty[i][j];
			}
				
			dfs(pnum - 1, day + 1);

			for (int j = 0; j < N; j++) {
				if (alive[j] == false) continue;
				score[j] -= guilty[i][j];
			}
			alive[i] = true;
		}
	}

	//day
	else {
		int max_score = 0;
		int kill=0;
		for (int i = 0; i < N; i++) {
			if (alive[i] == false) continue;
			if (max_score < score[i]) {
				max_score = score[i];
				kill = i;
			}
		}

		if (kill == jin) {
			if (ret < day) ret = day;
			return;
		}
		alive[kill] = false;
		dfs(pnum - 1, day);
		alive[kill] = true;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input();
	dfs(N, 0);

	cout << ret << endl;

	return 0;
}