[백준]6987 - 월드컵 (백트래킹)

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

6987번: 월드컵

input으로 각 나라의 승패 횟수가 주어졌을때 해당 예제가 가능한지 불가능하지 판별하는 문제

워낙 예외의 경우가 많기 때문에 전수조사 해야한다

 

	for (int i = 0; i < 5; i++) {
		for (int j = i + 1; j < 6; j++) {
			v.push_back({ i,j });
		}
	}

{0,1} = 1번팀과 2번 팀이 겨루는 경우

{0,2} = 1번팀과 3번 팀이 겨루는 겨우

...

{4,5} = 5번팀과 5번팀이 겨루는 경우

각 팀이 겨뤘을때를 체크하기위해 {i,j}쌍의 벡터를 만들어준다

 

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

		back(0);

input 값을 저장할 goal 배열과

탐색중에 값을 저장할 arr 배열을 선언,

arr 배열은 각 탐색마다 초기화해준다

 

그리고 백트래킹 함수 호출

 

void back(int depth) {
	if (depth == 15 ) {
		for (int i = 0; i < 6; i++) {
			for (int j = 0; j < 3; j++) {
				if (arr[i][j] != goal[i][j]) {
					return;
				}
			}
		}
		final = 1;
		return;
	}

백트래킹 함수는 재귀 함수로

모든 경기가 치뤄줬을때 해당 결과값이 input과 동일한지 체크.

동일하면 전역변수 final의 값을 1로 바꾼다

 

	int a, b;
	a = v[depth].first;
	b = v[depth].second;

	arr[a][0]++;
	arr[b][2]++;
	back(depth+1);
	arr[a][0]--;
	arr[b][2]--;

	arr[a][1]++;
	arr[b][1]++;
	back(depth+1);
	arr[a][1]--;
	arr[b][1]--;

	arr[a][2]++;
	arr[b][0]++;
	back(depth+1);
	arr[a][2]--;
	arr[b][0]--;

}

그 외엔 위에서 구한 벡터를 사용하여

a팀이 이겼을때, 비겼을때, b팀이 이겼을때

각각의 경우로 백트래킹 함수를 호출

 

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

int arr[6][3], goal[6][3], ans[4];
vector<pair<int, int>> v;
int final = 0;
void back(int);

int main() {


	for (int i = 0; i < 5; i++) {
		for (int j = i + 1; j < 6; j++) {
			v.push_back({ i,j });
		}
	}

	for (int k = 0; k < 4; k++) {
		final = 0;

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

		back(0);

		if (final == 1) ans[k] = 1;
		else
			ans[k] = 0;
		
	}
	for (int i = 0; i < 4; i++) {
		cout << ans[i] << " ";
	}
	return 0;


}

void back(int depth) {
	if (depth == 15 ) {
		for (int i = 0; i < 6; i++) {
			for (int j = 0; j < 3; j++) {
				if (arr[i][j] != goal[i][j]) {
					return;
				}
			}
		}
		final = 1;
		return;
	}
	int a, b;
	a = v[depth].first;
	b = v[depth].second;

	arr[a][0]++;
	arr[b][2]++;
	back(depth+1);
	arr[a][0]--;
	arr[b][2]--;

	arr[a][1]++;
	arr[b][1]++;
	back(depth+1);
	arr[a][1]--;
	arr[b][1]--;

	arr[a][2]++;
	arr[b][0]++;
	back(depth+1);
	arr[a][2]--;
	arr[b][0]--;

}

전체코드