BOJ 6987 월드컵

사용한 알고리즘

DFS, 완전탐색

알고리즘 설명

알고리즘은 그냥 완전 탐색이다.
여기서 dfs을 이용하여 이를 판단하는데, 총 6개의 팀과 6개의 경기가 있고 한 번씩만 경기를 하여 총 5번에 경기가 있다.
먼저 각각 5번의 경기를 진행하였는지 판단한다
위를 만족하면 다음 알고리즘을 진행한다.
먼저 팀 i와 팀 j가 경기를 한 번 하게 되는데 이때 승패 또는 무승부만 존재한다.
고로 팀이 승리를 한 경우 분명히 진팀이 있어야한다.
무승부와 같은 경우 자신을 제외한 다른 무승부팀이 있어야 한다.
이를 dfs 형태로 추적한다.
모든 승부가 매칭이 되면 이때 가능하며 모든 경우에 있어서 매칭이 존재하지 않으면 불가능한 경기표이다.

풀이

// baekjoon 6987 yechan
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int board[6][3];
bool visited[6][6][2];

bool dfs(int here) {
	if (here == 6) {
		for (int i=0; i<6; i++)
			for (int j=0; j<3; j++)
				if (board[i][j])
					return false;
		return true;
	}
	bool ret = false;
	if (board[here][0]) {
		for (int i=0; i<6; i++) {
			if (i == here) continue;
			if (!board[i][2]) continue;
			if (visited[here][i][0]) continue;
			visited[here][i][0] = visited[i][here][0] = true;
			board[here][0]--;
			board[i][2]--;
			ret = dfs(here);
			if (ret) return true;
			board[i][2]++;
			board[here][0]++;
			visited[here][i][0] = visited[i][here][0] = false;
		}
	}
	if (board[here][0]) return false;

	if (board[here][1]) {
		for (int i=0; i<6; i++) {
			if (i == here) continue;
			if (!board[i][1]) continue;
			if (visited[here][i][1]) continue;
			visited[here][i][1] = visited[i][here][1] = true;
			board[here][1]--;
			board[i][1]--;
			ret = dfs(here);
			if (ret) return true;
			board[i][1]++;
			board[here][1]++;
			visited[here][i][1] = visited[i][here][1] = false;
		}
	}
	if (board[here][1]) return false;
	return dfs(here+1);
}

int main() {
	for (int t=0; t<4; t++) {
		memset(visited, 0, sizeof(visited));
		bool flag = true;
		for (int i=0; i<6; i++) {
			int tmp = 0;
			for (int j=0; j<3; j++) {
				scanf("%d", &board[i][j]);
				tmp += board[i][j];
			}
			if (tmp != 5) flag = false;
		}
		printf("%d ", flag && dfs(0) ? 1 : 0);
	}
}