[백준] 월드컵

✔️ 문제

• 문제 링크 : https://www.acmicpc.net/problem/6987

✔️ 문제 이해

• 월드컵 조별 최종 예선의 결과가 4개 주어진다.
• 4개의 결과에 대하여 가능한 경우라면 1을 출력, 불가능한 경우라면 0을 출력한다.

✔️ 풀이

• 1개 조에 속한 6개 나라가 모두 경기를 한 후에 나올 수 있는 모든 경우의 수를 찾아본다.
• A팀과 B팀이 경기를 하고 나오는 결과는 3가지가 있다.
  1. A팀이 이긴다.
  2. 무승부
  3. A팀이 진다.
• 즉, 각 대진당 3가지의 경우가 있다.
• 6개의 나라는 서로 경기를 한 번씩 해야한다. 총 15번의 경기를 한다.
• 경기당 3가지의 경우의 수가 있다고 했으니, 총 3^15가지의 경우의 수가 있다.
• 3^15는 14,348,907이니 모든 경우를 찾아보는 구현이 가능하다.
• 주어진 케이스가 가능한 경우의 수라면, flag를 통해서 탐색을 중지하여 시간을 줄인다.

👨🏻‍💻 소스 코드

#include<iostream>
#include<vector>
#include<cstring>
#include <numeric>
using namespace std;

vector<vector<int>> gameResult(6, vector <int>(3, 0));
vector<vector<int>> candi(6, vector <int>(3, 0));

int aTeam[15] = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4 };
int bTeam[15] = { 1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4 ,5, 4, 5, 5 };
bool flag;

void dfs(int round) {
	if (flag) return;
		
	if (round == 15) {
		if (gameResult == candi) {
			flag = true;
		}
		return;
	}

	// a팀이 이기는 경우
	candi[aTeam[round]][0]++, candi[bTeam[round]][2]++;
	dfs(round + 1);
	candi[aTeam[round]][0]--, candi[bTeam[round]][2]--;
	
	// 무승부인 경우
	candi[aTeam[round]][1]++, candi[bTeam[round]][1]++;
	dfs(round + 1);
	candi[aTeam[round]][1]--, candi[bTeam[round]][1]--;

	// a팀이 지는 경우
	candi[aTeam[round]][2]++, candi[bTeam[round]][0]++;
	dfs(round + 1);
	candi[aTeam[round]][2]--, candi[bTeam[round]][0]--;
}

int main() {

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

		gameResult.assign(6, vector<int>(3, 0));
		candi.assign(6, vector<int>(3, 0));

		for (int i = 0; i < 6; i++) {
			for (int j = 0; j < 3; j++) {
				cin >> gameResult[i][j];
			}
		}

		flag = false;

		dfs(0);

		if (flag)
			cout << 1 << " ";
		else
			cout << 0 << " ";

	}
	
	return 0;
}

✔️ 문제 회고

• 벡터에 사용한 assign 함수는 이전에 벡터에 존재하던 원소는 모두 삭제하고, 인자로 받은 새로운 원소를 집어넣는 함수다.
• aTeam, bTeam 배열을 통해 미리 대진표를 짜놓고, 각 대진당 3가지 경우의 수를 찾는 아이디어가 필요했다.