[백준/BOJ] 백준 16986번 : 인싸들의 가위바위보

www.acmicpc.net/problem/16986

16986번: 인싸들의 가위바위보

지우가 낼 수 있는 모든 경우를 확인해서 이길 수 있는지 파악한다. 경기를 실행하는 것은 Solve(int match_a, int match_b, vector<deque<int>>& human, vector<int>& human_win) 함수를 이용했는데, match_a는 경기를 하는 사람 중 번호가 작은 사람, match_b는 경기를 하는 사람 중 번호가 큰 사람, human은 각각의 사람이 가위바위보 할때 낼 순서, human_win은 각각 사람들의 승리 수를 저장했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

int n, k;
int match[10][10];

bool Solve(int match_a, int match_b, vector<deque<int>>& human, vector<int>& human_win)
{
	//지우가 k승에 도달 했을때
	if (human_win[1] == k)
		return true;

	//지우가 아닌 사람이 k승에 도달 했을때
	if (human_win[2] == k || human_win[3] == k)
		return false;

	if (match_a == 1 && human[1].size() == 0) //지우가 경기에 참여하는데 더 이상 새로운거를 낼 수 없을때
		return false;

	if (human[1].size() + human_win[1] < k) //지우가 다 이겨도 k승에 도달 할 수 없을때
		return false;

	int not_match;

	if (match_a == 1)
	{
		if (match_b == 2)
			not_match = 3;

		else if (match_b == 3)
			not_match = 2;
	}

	else if (match_a == 2)
	{
		if (match_b == 3)
			not_match = 1;
	}

	int match_a_attack = human[match_a].front();
	human[match_a].pop_front();

	int match_b_attack = human[match_b].front();
	human[match_b].pop_front();

	if (match[match_a_attack][match_b_attack] == 2) //a가 b를 이길때
	{
		human_win[match_a]++;

		return Solve(min(not_match, match_a), max(not_match, match_a), human, human_win);
	}

	else if (match[match_a_attack][match_b_attack] == 1) //비길 때 (큰 숫자(뒤에 순서)가 이긴다)
	{
		human_win[match_b]++;

		return Solve(min(not_match, match_b), max(not_match, match_b), human, human_win);
	}

	else //b가 a를 이길때
	{
		human_win[match_b]++;

		return Solve(min(not_match, match_b), max(not_match, match_b), human, human_win);
	}

	return -1;
}

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

	cin >> n >> k;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			int input;
			cin >> input;

			match[i][j] = input;
		}

	deque<int> human2;
	deque<int> human3;

	//경희
	for (int i = 0; i < 20; i++)
	{
		int input;
		cin >> input;

		human2.push_back(input);
	}

	//민호
	for (int i = 0; i < 20; i++)
	{
		int input;
		cin >> input;

		human3.push_back(input);
	}

	//지우
	deque<int> human1;
	for (int i = 1; i <= n; i++)
	{
		human1.push_back(i);
	}

	//지우가 낼 수 있는 모든 경우를 확인
	sort(human1.begin(), human1.end());
	do {

		vector<deque<int>> human;
		deque<int> temp;
		human.push_back(temp);
		human.push_back(human1);
		human.push_back(human2);
		human.push_back(human3);

		vector<int> human_win(4, 0);

		if (Solve(1, 2, human, human_win))
		{
			cout << 1;
			return 0;
		}


	} while (next_permutation(human1.begin(), human1.end()));

	cout << 0;

	return 0;
}