[BOJ] 백준 6987 월드컵 (JAVA)

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

6987번: 월드컵

 

🔍 Solve

아주 예전에 단순히 승, 무, 패 숫자로만 비교해서 문제를 풀었을 때 실패했던 문제였는데,

그동안 재귀 부분 문제를 많이 풀어보고 다시 풀어보니 어렵지 않게 해결할 수 있었습니다.

 

해당 문제는 예제로 나와있는 그림과 테스트 케이스의 배열 형태가 같지 않아서 매번 입력을 받을 때마다 주춤하게 되는 것 같습니다. 하지만 손으로 매칭 결과를 그려보면 어렵지 않게 새로운 배열을 만들 수 있습니다.

 

저는 한 게임당 6팀의 승,무,패 정보를 가지는 game배열과 모든 팀의 경기 매칭 정보를 갖고 있는 match배열을 만들어주었습니다. 테스트 케이스의 첫 번째 경우, 만들어진 game배열과 match배열을 살펴보면 다음과 같습니다.

전역 변수로 isPossible를 만들어 해당 게임이 유효한지 검사합니다.

만약 한 팀의 경기 수가 5가 아니라면 isPossible는 false이고, 다음 게임을 탐색합니다.

 

matching함수에서 team1과 team2를 match배열에서 뽑아서 설정합니다.

해당 game배열의 값이 남아있다면 가능한 경우이므로, 승/무/패의 수에 따라 모든 경우를 검사합니다.

재귀를 돌리고 난 뒤, 꼭 원래 상태로 돌려놓아야 다음 검사에 영향 없이 탐색할 수 있습니다.

round의 수가 15로 모든 경기를 다 탐색했다면 해당 게임은 가능한 경우이므로 isPossible을 true로 설정합니다.

 

matching함수를 다 돌고난 뒤, isPossible이 true라면 1을 출력, false라면 0을 출력합니다.

 

❗ Code

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

public class Main {
    static int[][] game;
    static int[][] match = new int[15][2];
    static boolean isPossible;

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

        int idx = 0;
        for(int i=0;i<6;i++){
            for(int j=i+1;j<6;j++){  //게임 match 지정
                match[idx][0] = i;
                match[idx][1] = j;
                idx++;
            }
        }

        outer : for(int t=0;t<4;t++){
            st = new StringTokenizer(br.readLine());

            game = new int[6][3];

            for(int i=0;i<6;i++){ //6팀 각 이긴수, 비긴수, 진수
                int win = Integer.parseInt(st.nextToken());
                int draw = Integer.parseInt(st.nextToken());
                int lose = Integer.parseInt(st.nextToken());

                if(win+draw+lose!=5){  //한 팀의 경기 수가 5가 아니라면 불가
                    sb.append("0 ");
                    continue outer;
                }

                game[i][0] = win;
                game[i][1] = draw;
                game[i][2] = lose;
            }

            isPossible = false;
            matching(0);
            sb.append(isPossible? "1 ":"0 ");

        }
        System.out.println(sb);
    }

    private static void matching(int round){
        if(round==15){
            //15경기 다 가능하다면
            isPossible = true;
            return;
        }

        int team1 = match[round][0];
        int team2 = match[round][1];

        //승/무/패의 수가 남아있으면 모든 경우 검사
        if(game[team1][0] > 0 && game[team2][2] > 0){
            //team1:승, team2:패
            game[team1][0]--;
            game[team2][2]--;
            matching(round+1);
            //상태 다시 돌려놓기
            game[team1][0]++;
            game[team2][2]++;
        }
        if(game[team1][1] > 0 && game[team2][1] > 0){
            //team1:무, team2:무
            game[team1][1]--;
            game[team2][1]--;
            matching(round+1);
            //상태 다시 돌려놓기
            game[team1][1]++;
            game[team2][1]++;
        }
        if(game[team1][2] > 0 && game[team2][0] > 0){
            //team1:패, team2:승
            game[team1][2]--;
            game[team2][0]--;
            matching(round+1);
            //상태 다시 돌려놓기
            game[team1][2]++;
            game[team2][0]++;
        }
    }
}