[백준 6987] 월드컵

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

6987번: 월드컵

#include <cstdio>
#include <algorithm>

int game[6 + 2][3 + 2];
int num;
int choice[15 + 2][2 + 2];
int tmp[2 + 2];

void Combi(int n, int s)
{
	if (n == 2) {
		for (int i = 0; i < 2; i++) choice[num][i] = tmp[i];
		num++;
	}
	for (int i = s; i < 6; i++) {
		tmp[n] = i;
		Combi(n + 1, i + 1);
	}
}

int input(void)
{
	int flag = true;
	for (int i = 0; i < 6; i++) {
		int each = 0;
		for (int j = 0; j < 3; j++) {
			scanf("%d", &game[i][j]);
			each += game[i][j];
		}
		if (each != 5) flag = false;
	}
	//printf("flag : %d", flag);
	return flag;
}


int DFS(int n)
{
	if (n == num) return true;
	
	int t1 = choice[n][0];
	int t2 = choice[n][1];

	for (int i = 0; i < 3; i++) {
		if (game[t1][i] == 0) continue;
		if (game[t2][2 - i] == 0) continue;
		game[t1][i] -= 1;
		game[t2][2 - i] -= 1;
		if (DFS(n + 1)) return true;
		game[t1][i] += 1;
		game[t2][2 - i] += 1;
	}
	return false;
}


int main()
{
	Combi(0, 0);
	for (int t = 0; t < 4; t++) {
		std::fill(&game[0][0], &game[0][0] + sizeof(game) / sizeof(int), 0);
		if (input() && DFS(0)) printf("%d ", 1);
		else printf("%d ", 0);
	}
	return 0;
}

 

// Combi( ) 함수

6개국 중 2팀 씩 뽑아 진행할 수 있는 전체 경기의 수를 구하기 위함이다. 

A = 0, B = 1, C = 2, D = 3, E = 4, F = 5 와 같이 생각하고 choice 배열에 가능한 모든 조합의 수를 넣어주었다. 

 

 

// input( ) 함수

각 국가는 자신을 제외한 5개국과 경기를 진행한다. 

따라서 인덱스 i에 대하여 입력받은 모든 경기 수의 합은 5가 되어야 한다. 그렇지 않을 경우 불가능한 결과이므로, flag를 사용하여 false로 바꿔준다. 상기 조건이 맞지 않을 경우 바로 리턴해주지 않는 이유는, 입력을 받는 중이므로 해당 테스트케이스 이후에 영향을 줄 수 있기 때문이다. 따라서 일단 다 받아놓고, 각 팀 당 경기 수의 합이 5가 아닐 때 0을 출력하도록 구현했다. 

 

 

// DFS( ) 함수

6개국 중 2팀 씩 뽑아 진행할 수 있는 전체 경기의 수는 15이다. 그리고 각 경기마다 어떤 팀끼리 경기를 진행할지는 Combi 함수에서 만든 choice 배열을 참조할 수 있다. 

 

따라서 재귀 함수는 n이 15가 될 때 까지 (15변 경기를 진행하는데 인덱스 0부터 시작함) 호출되고, n번째 경기를 진행한다고 할 때, t1(첫번째 팀)은 choice[n][0], t2(두번째 팀)은 choice[n][1] 이 된다. 

그리고 (승, 패) (무, 무) (패, 승)과 같이 나올 수 있는 경기의 결과가 세가지이므로, 루프를 돌려 각 경우가 실제로 가능한지 체크한다.

만약 game[t1][i] == 0 이거나 game[t2][2 - i] == 0 이면 해당 경기결과는 불가능하기 때문에 무시한다. 

상기의 두 조건에 해당되지 않는다면 game[t1][i]와 game[t2][2 - i]를 하나씩 차감하고, 다음번 경기 진행을 위해 DFS(n + 1) 을 호출한다. 

또한 재귀함수가 리턴될 때 해당 경우 이외에 다른 경우도 탐색해야 하기 때문에, 다시 game[t1][i]와 game[t2][2 - i]를 하나씩 증가시켜준다.