BOJ 1079

28 Sep 2020 • ProblemSolving

마피아

문제출처

문제 해석

마피아 게임 규칙을 따라서 마피아가 살아남을 수 있는 최대 밤의 수를 구하는 문제입니다.

이 게임의 규칙은 다음과 같습니다.

  1. 참가자는 마피아,시민 그룹으로 나뉘어 있습니다.
  2. 참가자가 짝수 명 남았을 때는 밤입니다. 밤에는 마피아가 죽일 사람을 한명 고릅니다.
  3. 참가자가 홀수 명 남았을 때는 시민이 한명을 죽입니다.
  4. 만약 게임에 마피아가 한명도 안남았으면 시민팀 승, 그 반대면 마피아팀 승입니다.

게임은 다음과 같이 진행됩니다.

  1. 밤에는 마피아가 죽일 사람한명 고릅니다. 이후 유죄지수가 바뀝니다.
  2. 낮에는 유죄지수가 가장 높은사람을 죽입니다.

설계(15)

N<=16이므로 완전탐색으로 풀이가 가능해보입니다.

마피아가 남은 사람들을 죽일 방법을 고르는데 원래는 o(15!)이라고 생각할 지도 모르겠지만, 낮에는 무조건 한사람씩 죽이므로 최악의 경우 15x13x11x…x1 = 약 O(200만)정도로 충분히 시간안에 풀이가 가능할 것입니다.

백트래킹 방식으로 죽일 사람 정하고 유죄지수 변화시키는 것을 반복하여 최대 일수를 구합니다.

구현(20)

코드1(Naive)
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

#define MAXN 16

int R[MAXN][MAXN];
vector<pair<int,int> > guilty;
int N;
int ans;
int target;
void go(int count,int night) {
	if (count == 0) return;
	vector<pair<int, int> > tmp_v = guilty;
	if (count % 2 == 0) {
		for (int i = 0; i < guilty.size(); i++) {
			if (guilty[i].first == target) continue;
			vector<pair<int, int> > tmp1;
			for (int j = 0; j < guilty.size(); j++) {
				if (i == j) continue;
				int idx = guilty[j].first;
				int value = guilty[j].second + R[guilty[i].first][idx];
				tmp1.push_back({ idx,value });
			}
			
			guilty = tmp1;
			go(count - 1,night+1);
			guilty = tmp_v;
		}
	}
	else {
		int max_v = -300;
		int max_node = 0;
		int max_target = 0;
		for (int i = 0; i < guilty.size(); i++) {
			if (guilty[i].second > max_v) {
				max_v = guilty[i].second;
				max_node = i;
				max_target = guilty[i].first;
			}
		}
		if (max_target == target) {
			if (ans < night) ans = night;
			return;
		}
		guilty.erase(guilty.begin() + max_node);
		go(count - 1,night);
		guilty = tmp_v;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	guilty.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> guilty[i].second;
		guilty[i].first = i;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> R[i][j];
		}
	}
	cin >> target;
	go(N,0);
	cout << ans << "\n";
	return 0;
}

코드 1의 경우 vector에 정보들을 추가하고 삭제하는 방식을 사용하였습니다. 그 결과 760ms가 나왔습니다. 좀더 최적화가 필요해보입니다.

코드2(최적화1)
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

#define MAXN 16

int R[MAXN][MAXN];
bool dead[MAXN];
int guilty[MAXN];
int N;
int ans;
int target;
void go(int count,int night) {
	if (count == 0) return;
	
	if (count % 2 == 0) {
		for (int i = 0; i < N; i++) {
			if (i == target || dead[i]) continue;
			int temp[MAXN] = { 0, };
			memcpy(temp, guilty, sizeof(guilty));
			for (int j = 0; j < N; j++) {
				if (i == j || dead[j]) continue;
				guilty[j] += R[i][j];
			}
			dead[i] = true;
			go(count - 1,night+1);
			dead[i] = false;
			memcpy(guilty, temp, sizeof(temp));
		}
	}
	else {
		int max_v = -300;
		int max_node = 0;
		int max_target = 0;
		for (int i = 0; i < N; i++) {
			if (dead[i]) continue;
			if (guilty[i]> max_v) {
				max_v = guilty[i];
				max_node = i;
			}
		}
		if (max_node == target) {
			if (ans < night) ans = night;
			return;
		}
		dead[max_node] = true;
		go(count - 1,night);
		dead[max_node] = false;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> guilty[i];
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> R[i][j];
		}
	}
	cin >> target;
	go(N,0);
	cout << ans << "\n";
	return 0;
}

코드 2의 경우, vector를 사용하지 않고 정적 배열을 이용하여 이전 상태를 저장해놓아서 복사해줌으로써 되돌리는 방식을 이용하였습니다. 그 결과 328ms가 나왔습니다. 맞은사람들을 보면 훨씬 빠른 코드를 작성한 것을 볼 수 있었습니다. 뭔가 더 최적화할 수 있을 것 같습니다.

코드3(최적화2)
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

#define MAXN 16

int R[MAXN][MAXN];
bool dead[MAXN];
int guilty[MAXN];
int N;
int ans;
int target;
bool finished;
void go(int count,int night) {
	if (finished) return;
	if (dead[target] || count == 1) {
		if (ans < night) ans = night;
		if (count == 1) finished = true;
		return;
	}
	if (count == 0) return;
	
	if (count % 2 == 0) {
		for (int i = 0; i < N; i++) {
			if (i == target || dead[i]) continue;
			int temp[MAXN] = { 0, };
			for (int j = 0; j < N; j++) {
				temp[j] = guilty[j];
			}
			for (int j = 0; j < N; j++) {
				if (i == j || dead[j]) continue;
				guilty[j] += R[i][j];
			}
			dead[i] = true;
			go(count - 1,night+1);
			dead[i] = false;
			for (int j = 0; j < N; j++) {
				guilty[j] = temp[j];
			}
		}
	}
	else {
		int max_v = -300;
		int max_node = 0;
		for (int i = 0; i < N; i++) {
			if (dead[i]) continue;
			if (guilty[i]> max_v) {
				max_v = guilty[i];
				max_node = i;
			}
		}		
		dead[max_node] = true;
		go(count - 1,night);
		dead[max_node] = false;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> guilty[i];
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> R[i][j];
		}
	}
	cin >> target;
	go(N,0);
	cout << ans << "\n";
	return 0;
}

가능한 경우를 모두 조사하지 않는 방법을 떠올려볼 필요가 있습니다. 만약 마피아 본인 혼자 남았다면 해당 밤 수가 최대인 것을 알 수 있습니다. 그러므로 boolean변수로 마피아 혼자남은경우를 체크하여, 이후에 재귀문을 돌지 않도록 최적화를 시켜주었습니다. 그 결과 80ms가 나왔습니다.

디버깅
제출결과
  • 760ms(naive)
  • 328ms(최적화1)
  • 80ms(최적화2)

마무리

완전탐색을 하는 문제였습니다. 정답률이 매우 낮길래 조심스럽게 접근하였는데 딱히 그럴 필요가 없었습니다. 최적화 여부에 따라서 성능차이가 많이 나는 것을 볼 수 있었습니다.

 BOJ

Related Posts