[백준/BOJ] 백준 6987번 : 월드컵

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

6987번: 월드컵

 

각 나라가 싸우는 경우를 확인하여 입력으로 받은 상태에 도달할 수 있는지 확인했다. 그런데, 모든 경우를 확인하는 건 아니고 입력으로 받은 상태에 도달할 가능성이 존재할 때만 확인을 해 나아갔다. 예를 들어, A팀과 B팀이 싸우는데, 입력받은 상태의 A팀의 승리 횟수는 1, B팀의 패배 횟수가 0이라면, A가 B를 이기는 경우가 있지 않은 것이므로 A가 B를 이기는 경우는 탐색해 나아가지 않는다.

 

코드

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

int n;
vector<int> output;

//가능한 모든 경우의 수 확인

//here팀이 fight팀과 싸울때 경우의 수 확인
int solve(int here, int fight, vector<int>& status, vector<int>& check) {

	//here팀이 싸우는 모든 경우의 수를 확인 했을때
	if (fight == 6) {

		//전체 모든 경우의 수를 확인 했을때
		if (here == 4) {
			if (check == status) {
				return 1;
			}
			else {
				return 0;
			}
		}

		return solve(here + 1, here + 2, status, check);
	}

	int ret = 0;

	//here의 승리일때(fight의 패배)
	//승리해도 check에 도달할 수 있는지 확인
	if (status[here * 3 + 0] + 1 <= check[here * 3 + 0] && status[fight * 3 + 2] + 1 <= check[fight * 3 + 2]) {
		status[here * 3 + 0]++;
		status[fight * 3 + 2]++;
		ret |= solve(here, fight + 1, status, check);
		status[here * 3 + 0]--;
		status[fight * 3 + 2]--;
	}

	//무승부일때
	//무승부여도 check에 도달할 수 있는지 확인
	if (status[here * 3 + 1] + 1 <= check[here * 3 + 1] && status[fight * 3 + 1] + 1 <= check[fight * 3 + 1]) {
		status[here * 3 + 1]++;
		status[fight * 3 + 1]++;
		ret |= solve(here, fight + 1, status, check);
		status[here * 3 + 1]--;
		status[fight * 3 + 1]--;
	}


	//here의 패배일때(fight의 승리)
	//패배여도 check에 도달할 수 있는지 확인
	if (status[here * 3 + 2] + 1 <= check[here * 3 + 2] && status[fight * 3 + 0] + 1 <= check[fight * 3 + 0]) {
		status[here * 3 + 2]++;
		status[fight * 3 + 0]++;
		ret |= solve(here, fight + 1, status, check);
		status[here * 3 + 2]--;
		status[fight * 3 + 0]--;
	}

	return ret;
}

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

	for (int t = 0; t < 4; t++) {

		vector<int> check;
		for (int i = 0; i < 18; i++) {
			int input;
			cin >> input;
			check.push_back(input);
		}

		vector<int> status(18, 0);
		int result = solve(0, 1, status, check);
		output.push_back(result);
	}

	for (int i = 0; i < output.size(); i++) {
		cout << output[i] << " ";
	}

	return 0;
}