백준 6987. 월드컵 :: 돼지개발자

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

"가능한 모든 경기 결과를 탐색해 주어진 결과를 만족하는 경우가 있는지 찾자"

처음 이 문제를 너무 단순하게 생각했다. 각 조에서 이루어진 경기 결과 중 승과 패가 같고, 무승부인 경우가 짝수개로 나오는지만 확인하면 되는 줄 알고, 그렇게 해서 애를 먹었다.. 

제대로된 접근 방법은 각 조의 6개의 국가가 돌아가면서 모두 한번씩 경기를 치룬다고 했으니 가능한 경기는 아래와 같이 총 15개 이다.

A : {B,C,D,E,F}

B : {C,D,E,F}

C : {D,E,F}

D : {E,F}

E : {F}

경기의 순서는 상관 없다. 이 15개의 경기에서 매 경기 가능한 결과 (A 가 이기고 B가 지고 , B가 지고 B가 이기고, A 와 B가 무승부 인 경우)

최대 세가지 경우에 대해 DFS 탐색을 한다. 물론 주어진 결과에 따라 가능한 경우만 탐색한다. 예를들면, 주어진 A의 승무패가 0/0/1 일 때는 A가 이기는 경우, A가 비기는 경우는 없다. DFS 탐색 하는 과정에서 백트래킹을 사용해야 한다. 

나의 경우엔 G1 과 G2 배열을 두어 가능한 15개의 국가 index를 미리 정해두었다. 숫자가 커진다면, for문으로 돌려서 해당 배열을 생성해야 겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    static int[] g1 = {0,0,0,0,0,1,1,1,1,2,2,2,3,3,4};
    static int[] g2 = {1,2,3,4,5,2,3,4,5,3,4,5,4,5,5};
    static int[] win = new int[6];
    static int[] draw = new int[6];
    static int[] lose = new int[6];
    static boolean ok;
    static StringBuffer sb = new StringBuffer();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        for (int t = 0; t < 4; t++) {
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int sw = 0;
            int sd = 0;
            int sl = 0;
            ok = false;
            
            for (int i = 0; i < 6; i++) {
                sw += win[i] = Integer.parseInt(st.nextToken());
                sd += draw[i] = Integer.parseInt(st.nextToken());
                sl += lose[i] = Integer.parseInt(st.nextToken());
            }
            // 총 승/무/패의 합은 30이 되어야함.
            if(sw+ sd + sl != 30) {
                ok = false;
            }
            else {
                solve(0);
            }
            sb.append((ok ? 1 : 0) +" ");
        }
        System.out.println(sb.toString());
    }
    
    static void solve(int game) {
        if(ok) return ;
        
        // 마지막 게임까지 왔다면, 가능한경우
        if(game == 15) {
            ok = true;
            return ;
        }
        
        int t1 = g1[game];    // team 1
        int t2 = g2[game];    // team 2
        
        // team 1의 승리가 가능하다면
        if(win[t1] > 0 && lose [t2] >0) {
            win[t1]--;
            lose[t2]--;
            solve(game+1);
            win[t1]++;
            lose[t2]++;
        }
        // team 2의 승리가 가능하다면
        if(lose[t1] > 0 && win [t2] >0) {
            lose[t1]--;
            win[t2]--;
            solve(game+1);
            lose[t1]++;
            win[t2]++;
        }
        // team 1,2 가 무승부가 가능하다면
        if(draw[t1] > 0 && draw[t2] >0) {
            draw[t1]--;
            draw[t2]--;
            solve(game+1);
            draw[t1]++;
            draw[t2]++;
        }    
    }
}