6987 월드컵 (Java)

월드컵

문제

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

나라    승    무      패
A      5      0      0
B      3      0      2
C      2      0      3
D      0      0      5
E      4      0      1
F      1      0      4    
나라    승    무      패
A      4      1      0
B      3      0      2
C      4      1      0
D      1      1      3
E      0      0      5
F      1      1      3    
나라    승    무      패
A      5      0      0
B      4      0      1
C      2      2      1
D      2      0      3
E      1      0      4
F      0      0      5    
나라    승    무      패
A      5      0      0
B      3      1      1
C      2      1      1
D      2      0      3
E      0      0      5
F      1      0      4

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

입력

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

출력

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

풀이

경기는 모든 팀이 서로 한경기씩 진행한다.
주의할 점은 A-B 경기를 하면 B-A경기는 동일하기 때문에 한번 더 진행하지 않아도 된다.
즉 총 경기는
A : B C D E F
B : C D E F
C : D E F
.
.
.
F : G
총 15개의 경기가 이루어진다.
경기를 진행하는 경우의 수를 미리 저장해두고 ex) 배열 두개를 사용 int[] t1, int[] t2
경기를 하나씩 진행하며 할 수 있는 모든 경우의 수를 확인한다.
주의할 점은 경기의 승,패를 진행할 때 해당 팀에 남아있는 승리 수 or 패배 수가 존재해야 한다.
하나씩 대입하여 백트레킹을 진행했을 때 15번째 경기까지 완료가 된다면 가능한 결과이다.

코드

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

public class Main{

    static int[] t1;
    static int[] t2;
    static int[] win;
    static int[] draw;
    static int[] lose;
    static boolean isOk;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int cnt = 0;
        t1 = new int[15];
        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;
            }
        }

        String ans = "";
        win = new int[6];
        draw = new int[6];
        lose = new int[6];
        for (int i = 0; i < 4; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int total = 0;

            for (int j = 0; j < 6; j++) {
                total += win[j] = Integer.parseInt(st.nextToken());
                total += draw[j] = Integer.parseInt(st.nextToken());
                total += lose[j] = Integer.parseInt(st.nextToken());

            }
            isOk = false;

            if(total == 30)
                backTracking(0);

            if (isOk) {
                ans += "1 ";
            } else {
                ans += "0 ";
            }


        }


        System.out.println(ans.trim());

    }

    static void backTracking(int depth) {
        if (isOk) {
            return;
        }
        if (depth == 15) {
            isOk = true;
            return;
        }

        int a = t1[depth];
        int b = t2[depth];

        //t1 win
        if (win[a] > 0 && lose[b] > 0) {
            win[a]--;
            lose[b]--;
            backTracking(depth + 1);
            win[a]++;
            lose[b]++;
        }

        // draw
        if (draw[a] > 0 && draw[b] > 0) {
            draw[a]--;
            draw[b]--;
            backTracking(depth + 1);
            draw[a]++;
            draw[b]++;
        }

        //t1 lose
        if (lose[a] > 0 && win[b] > 0) {
            lose[a]--;
            win[b]--;
            backTracking(depth + 1);
            lose[a]++;
            win[b]++;
        }

    }


}