[백준 6987] 월드컵 (Java)

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

6987번: 월드컵

1. 주의할 점

- 경우의수를 직접 구현해보려다가 실패했다. Set도 생각해 봤지만 그 팀의 가능한 승무패인지 확인만 해줄 뿐 그 이상의 가치는 없다. 즉, DFS로 풀자

 

2. 구현

- 토너먼트 형식으로 이루어져 있으므로, A팀과 B팀이 붙을 수 있는 경우의 수를 미리 구하여 T1[], T2[]에 넣는다

- 각 라인별을 6등분해서 3개씩 입력받아 한팀에 대한 정보를 Win[], Draw[], Lose[]에 담는다

- 만약 전체 팀의 경기수가 30이 안된다면 잘못된 경우로 간주한다(N*(N-1)번 만큼 경기가 이뤄져야 한다. 양쪽의 입장에서 간주하므로 2로 나누지 않는다)

- DFS를 수행하며 15번의 경기가 성공적으로 수행되면 Avail=true로 바꾼다. DFS의 경우 A가 이기거나, 비기거나, 지거나 총 3가지의 경우를 따져보며, 해당 경우일 때 Win[],Draw[],Lose[]의 값이 1 이상일때만 수행한다.

 

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

public class Main_bj_6987_월드컵 {
	static int win[],lose[],draw[],t1[],t2[];
	static HashMap<String, String> map;
	static boolean avail;
	
	static void dfs(int idx) {
		if(avail) return;
		if(idx==15) {
			avail=true;
			return;
		}
		int a = t1[idx];
		int b= t2[idx];
		//a가 이기는 경우
		if(win[a]>0 && lose[b]>0) {
			win[a]--;
			lose[b]--;
			dfs(idx+1);
			win[a]++;
			lose[b]++;
		}
		//a와 b가 비기는 경우
		if(draw[a]>0 && draw[b]>0) {
			draw[a]--;
			draw[b]--;
			dfs(idx+1);
			draw[a]++;
			draw[b]++;
		}
		//a가 지는 경우
		if(lose[a]>0 && win[b]>0) {
			lose[a]--;
			win[b]--;
			dfs(idx+1);
			lose[a]++;
			win[b]++;
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int cnt=0;
		t1 = new int[15];		//경기하는 2팀
		t2 = new int[15];
		for(int i=0;i<5;i++) {
			for(int j=i+1;j<6;j++) {
				t1[cnt]=i;
				t2[cnt++]=j;
			}
		}
		for(int i=0;i<4;i++) {
			String s = br.readLine();
			StringTokenizer st = new StringTokenizer(s);
			win = new int[6];		
			lose = new int[6];		
			draw = new int[6];	
			avail=false;			
			int w=0,l=0,d=0;
			for(int j=0;j<6;j++) {
				w += win[j] = Integer.parseInt(st.nextToken());
				d += draw[j] = Integer.parseInt(st.nextToken());
				l += lose[j] = Integer.parseInt(st.nextToken());
			}
			if(w+d+l!=30)
				avail=false;
			else
				dfs(0);
			if(avail) System.out.print(1+" ");
			else System.out.print(0+" ");
		}
	}
}