백준 - 월드컵(JAVA)

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

6987번: 월드컵

문제설명

 

6팀의 모든 경우의 수를 탐색하는 문제이다. 재귀와 백트래킹을 이용하여 해결한다.

 

알고리즘

1. 재귀를 이용하는데 종료조건은 무사히 15경기까지 오는 것이다.

 

2. 각 팀의 승리 , 패배 , 무승부 횟수가 음수가 되면 return 한다.

 

3. 1팀은 2,3,4,5,6 팀과 경기 2팀은 3,4,5,6 경기 3팀은 4,5,6 ~~ 이런식으로 진행된다.

-> team, index 변수 사용

 

주의사항

1. 승 패 무승부 합쳐 30개가 안되는 TK가 존재한다.

 

2. 백 트래킹 조건은 종료조건 보다 위에 배치한다.

 

구현

 

public class Main_월드컵 {
    static int win[];
    static int lose[];
    static int draw[];
    static boolean flag;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        win = new int[6];
        lose = new int[6];
        draw = new int[6];
        for (int j = 0; j < 4; j++) {
            int sum=0;
            StringTokenizer s = new StringTokenizer(in.readLine()," ");
            for (int i = 0; i < 6; i++) {
                sum+=win[i] = Integer.parseInt(s.nextToken());
                sum+=draw[i] = Integer.parseInt(s.nextToken());
                sum+=lose[i] = Integer.parseInt(s.nextToken());
            }
            flag = false;
            if(sum == 30) //TK방지
                DFS(0,0,1);
            System.out.print((flag==false?"0":"1")+" ");
        }

    }

    private static void DFS(int team,int cnt,int index) {
//        System.out.println(Arrays.toString(win));
//        System.out.println(Arrays.toString(lose));
//        System.out.println(Arrays.toString(draw));
//        System.out.println(cnt);
        if(flag) //성공 조건 맞으면 빠르게 종료하기 위함
            return;
        if(win[team] < 0 || lose[team] <0 || draw[team]<0 ||win[team+index-1] < 0 || lose[team+index-1] <0 || draw[team+index-1]<0)
            return;
        if(cnt == 15) //15게임까지가면
        {
            flag = true;
            return;
        }

        //////////////팀바꿈  -> 경우의 수 1팀 - 2,3,4,5,6 2팀 - 3,4,5,6 3팀 - 4,5,6 -> 구현///////////////
        if(cnt == 5) //5경기끝나면 팀+1 index초기화 
        {
            team++;
            index=1;
        }
        else if(cnt == 9)
        {
            team++;
            index=1;
        }
        else if(cnt == 12)
        {
            team++;
            index=1;
        }
        else if(cnt == 14)
        {
            team++;
            index=1;
        }

        //a가 이기고 b가 질때
        win[team]--;
        lose[team+index]--;
        DFS(team,cnt+1,index+1);
        win[team]++;
        lose[team+index]++;
        //a가 지고 b가 이길때
        win[team+index]--;
        lose[team]--;
        DFS(team,cnt+1,index+1);
        win[team+index]++;
        lose[team]++;
        //무승부일때
        draw[team]--;
        draw[team+index]--;
        DFS(team,cnt+1,index+1);
        draw[team]++;
        draw[team+index]++;

    }

}