[백준, BOJ 6987] 월드컵 (java)

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

6987번: 월드컵

---

문제

월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부, 패의 수가 가능한 결과인지를 판별하려고 한다. 다음은 가능한 결과와 가능하지 않은 결과의 예이다.

네 가지의 결과가 주어질 때 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄부터 넷째 줄까지 각 줄마다 6개국의 결과가 나라별로 승, 무승부, 패의 순서로 빈칸을 하나 사이에 두고 18개의 숫자로 주어진다. 승, 무, 패의 수는 6보다 작거나 같은 자연수 또는 0이다.

출력

입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 1, 불가능한 결과는 0을 빈칸을 하나 사이에 두고 출력한다.

 

예제 입력 1

5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4
4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3
5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5
5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4

예제 출력 1

 

1 1 0 0

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int[][][] arr;
	static int[][] tmp;
	static int[] result;
	
	private static void vs(int a, int b) {
		
		// 하나의 경우가 나왔을 때
		if(a == 5) {
			for (int i = 0; i < 4; i++) {
				if(result[i] == 0) { // 아직 불가능한 결과인 테스트 케이스 중에
					int check = 1 << 6; // 원래 boolean 배열로 check 확인해줬는데, 메모리 부족으로 비트마스킹으로 대체
					int j = 0, k = 0;
					for (j = 0; j < 6; j++) { // 나올 수 있는 결과 tmp와 결과를 비교
						for (k = 0; k < 6; k++) {
							if(arr[i][j][0] == tmp[k][0] && arr[i][j][1] == tmp[k][1] && arr[i][j][2] == tmp[k][2] && (check >> k) % 2 == 0) {
								check |= 1 << k;
								break;
							}
						}
						if(k == 6) break;
					}
					// 결과가 같았는지 확인
					if(k != 6) {
						result[i] = 1;
					}
				}
			}
			
			return;
		}
		
		// a가 이긴 경우
		tmp[a][0]++;
		tmp[b][2]++;
		if(b == 5) vs(a + 1, a + 2);
		else vs(a, b + 1);
		tmp[a][0]--;
		tmp[b][2]--;
		
		// 무승부
		tmp[a][1]++;
		tmp[b][1]++;
		if(b == 5) vs(a + 1, a + 2);
		else vs(a, b + 1);
		tmp[a][1]--;
		tmp[b][1]--;
		
		
		// a가 진 경우
		tmp[a][2]++;
		tmp[b][0]++;
		if(b == 5) vs(a + 1, a + 2);
		else vs(a, b + 1);
		tmp[a][2]--;
		tmp[b][0]--;
	}

	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		// 6개국 결과 받기
		arr = new int[4][6][3];
		for (int i = 0; i < 4; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 6; j++) {
				for (int k = 0; k < 3; k++) {
					arr[i][j][k] = Integer.parseInt(st.nextToken());
				}
			}
		}
		
		// 나올 수 있는 결과
		tmp = new int[6][3];
		
		// 결과
		result = new int[4];
		
		// 경우의 수 구하기
		vs(0, 1);
		
		// 출력
		for (int i = 0; i < 4; i++) {
			sb.append(result[i] + " ");
		}
		System.out.println(sb);
	}
}