취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6987번 문제인 월드컵이다.
문제는 아래 링크를 확인하자.

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

6개국이 각 국가쌍마다 한번씩 리그전을 펼친다면 총 경기의 수는 15개가 된다. 각 경기는 팀별로 승, 패, 무의 세 가지 경우가 존재하므로 총 경기결과의 경우의 수는 3^15 = 14,348,907가지라는 점을 관찰하자.

따라서, 주어진 승패의 결과를 이용해 각 경기 결과를 한 팀의 승, 패, 무로 가정하는 백트래킹 코드를 작성해 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[18];

bool func(int i, int j) {
	if (j == 6) return 1;
	else {
		int ii, jj;
		if (i + 1 < j) ii = i + 1, jj = j;
		else ii = 0, jj = j + 1;
		
		if (arr[i * 3] && arr[j * 3 + 2]) {
			arr[i * 3]--, arr[j * 3 + 2]--;
			if (func(ii, jj)) return 1;
			arr[i * 3]++, arr[j * 3 + 2]++;
		}
		if (arr[i * 3 + 1] && arr[j * 3 + 1]) {
			arr[i * 3 + 1]--, arr[j * 3 + 1]--;
			if (func(ii, jj)) return 1;
			arr[i * 3 + 1]++, arr[j * 3 + 1]++;
		}
		if (arr[i * 3 + 2] && arr[j * 3]) {
			arr[i * 3 + 2]--, arr[j * 3]--;
			if (func(ii, jj)) return 1;
			arr[i * 3 + 2]++, arr[j * 3]++;
		}
	}

	return 0;
}

void solve() {
	int total = 0;
	for (int k = 0; k < 18; k++) {
		cin >> arr[k];
		total += arr[k];
	}
	if (func(0, 1) && total == 30) cout << 1 << ' ';
	else cout << 0 << ' ';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int T = 0; T < 4; T++) solve();
}