[BOJ] 월드컵(JAVA)

[6987] 월드컵

www.acmicpc.net/problem/6987

 

Solution

• 국가별로 같은 조에 속한 나라들과 1번씩 총 5번의 경기를 치루기 때문에, matches 배열에 경기 순서를 미리 정의했다.
• matches 배열에 순서대로 접근하면서 backtracking(count+1) 메서드를 dfs로 호출하고, 옳은 결과를 유지하면서 count==15가 되었을 때 탐색을 종료한다.
• 총 15 번의 경기만 치루기 때문에 count==15까지 도달했다는 것은 모든 경기가 주어진 결과에 부합한다는 것을 의미한다.

 

 

소스코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int[][] matches = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}};
    static int[][] result;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int i = 0; i < 4; i++) {
            result = new int[6][3];
 
            // input
            int sum = 0;
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 6; j++) {
                for (int k = 0; k < 3; k++) {
                    result[j][k] = stoi(st.nextToken());
                    sum += result[j][k];
                }
            }
 
            boolean valid = backtracking(0);
            if (sum == 30 && valid) sb.append(1 + " ");
            else sb.append(0 + " ");
        }
        System.out.println(sb.toString().trim());
    }
 
    private static boolean backtracking(int count) {
        if (count == 15) return true;
 
        // 승 : 패
        if (result[matches[count][0]][0] > 0 && result[matches[count][1]][2] > 0) {
            result[matches[count][0]][0]--;
            result[matches[count][1]][2]--;
            if (backtracking(count + 1)) return true;
            result[matches[count][0]][0]++;
            result[matches[count][1]][2]++;
        }
 
        // 무 : 무
        if (result[matches[count][0]][1] > 0 && result[matches[count][1]][1] > 0) {
            result[matches[count][0]][1]--;
            result[matches[count][1]][1]--;
            if (backtracking(count + 1)) return true;
            result[matches[count][1]][1]++;
            result[matches[count][0]][1]++;
        }
 
        // 패 : 승
        if (result[matches[count][0]][2] > 0 && result[matches[count][1]][0] > 0) {
            result[matches[count][0]][2]--;
            result[matches[count][1]][0]--;
            if (backtracking(count + 1)) return true;
            result[matches[count][1]][0]++;
            result[matches[count][0]][2]++;
        }
 
        return false;
    }
 
    private static int stoi(String s) {
        return Integer.parseInt(s);
    }
}