[BOJ] 6987. 월드컵

처음에 보고 아이디어를 떠올리기 상당히 어려웠던 문제이다.

이 문제에서 전체 경우의 수를 따져본다면 전체 6팀이 경기를 하기때문에 총 15경기가 열리고, 경기마다 승,무,패 의 경우가 있기에 전체 3^15가지의 경우가 생기게 된다. 그러므로 백트래킹을 사용하여 승무패를 계속 재귀적으로 호출하면서 전체경우의 수랑 현재 테이블이랑 같아지는지 확인하여 구할수 있다.

백트래킹 문제라 전혀 생각지 못한 문제였다. 문제를 깊이 생각할 필요가 있다고 느꼈다.

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_6987_월드컵 {
    
    static int[] team1= {0,0,0,0,0,1,1,1,1,2,2,2,3,3,4};
    static int[] team2= {1,2,3,4,5,2,3,4,5,3,4,5,4,5,5};
    static int[][] result;
    static int[][] table;
    
    
    static boolean possible;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        for(int tc=1;tc<=4;tc++) {
            st=new StringTokenizer(br.readLine());
            result=new int[6][3];
            table=new int[6][3];
            int sum=0;
            for(int i=0;i<6;i++) {
                table[i][0]=Integer.parseInt(st.nextToken());
                table[i][1]=Integer.parseInt(st.nextToken());
                table[i][2]=Integer.parseInt(st.nextToken());
                sum+=(table[i][0]+table[i][1]+table[i][2]);
            }
            if(sum!=30) {
                System.out.println(0);
                continue;
            }
            possible=false;
            dfs(0);
            System.out.println(possible?1:0);
            
        }
        
    }
    
    static void dfs(int depth) {
        if(possible==true)
            return;
        
        if(depth==15) {
            for(int i=0;i<6;i++) {
                for(int j=0;j<3;j++) {
                    if(table[i][j]!=result[i][j])
                        return;
                }
            }
            
            possible=true;
            return;
        }
        
        int home=team1[depth];
        int away=team2[depth];
        
        //승, 볼필요가 있다면
        if(table[home][0]>0 && table[away][2]>0) {
            result[home][0]+=1; result[away][2]+=1;
            dfs(depth+1);
            result[home][0]-=1; result[away][2]-=1;
        }
    
        
        //무, 볼필요가 있다면
        if(table[home][1]>0 && table[away][1]>0) {
            result[home][1]+=1; result[away][1]+=1;
            dfs(depth+1);
            result[home][1]-=1; result[away][1]-=1;
        }
        
        //패, 볼필요가 있다면
        if(table[home][2]>0 && table[away][0]>0) {
            result[home][2]+=1; result[away][0]+=1;
            dfs(depth+1);
            result[home][2]-=1; result[away][0]-=1;
        }
    }
}