BJ S3 6987 월드컵

BOJ S3 6987 월드컵

 

 

문제링크

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

6987번: 월드컵

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=O0G5QrCMAhE&feature=youtu.be

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.silver.l3;

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

/**
 * @author itsmeyjc
 * @since 2020. 3. 15.
 * @see https://www.acmicpc.net/problem/6987
 * @mem 14100
 * @time 76
 * @caution #dfs
 * 승 패에 대한 정보가 있을 때 0이 될 때까지 빼가며 전체 케이스를 찾아본다.
 */
public class BJ_S3_6987_월드컵 {
    static StringBuilder sb = new StringBuilder();
    static int[][] score = null;

    static int A;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new StringReader(src));
        score = new int[4][18];
        StringTokenizer tokens;
        // 각각의 row 별로 판단해주자.
        for (int r = 0; r < 4; r++) {
            tokens = new StringTokenizer(br.readLine());
            for (int c = 0; c < 18; c++) {
                score[r][c] = Integer.parseInt(tokens.nextToken());
            }
            A = 0;
            dfs(0, 1, score[r]);
            sb.append(A).append(" ");
        }

        System.out.println(sb);
    }


    /**
     * game은 a-{b,c,d,e,f}, b-{c,d,e,f}, c-{d,e,f}, d-{e,f}, e-{f}로 이뤄지므로 상대팀이 f 즉 6이 되면
     * 팀 배치를 우리 팀부터 변경해준다.
     */
    static void dfs(int teamA, int teamB, int[] score) {
        // 상대팀이 6을 넘어가면 우리 팀이 변경되어야 한다.
        if (teamB == 6) {
            dfs(teamA + 1, teamA + 2, score);
            return;
        }
        // System.out.println("next team: " + (char) (teamA + 'A') + "," + teamA + " : " + (char) (teamB + 'A') + "," + teamB);
        if (teamA > 4) {
            // 솔루션 실행 - 하나라도 0이 아닌게 있으면 0 아니면 1
            for (int c = 0; c < score.length; c++) {
                if (score[c] > 0) {
                    A = 0;
                    return;
                }
            }
            A = 1;
            return;
        }

        // 각 팀별로 이기고, 비기고 질 때 체크 i=0, j=2 --> teamB 승, i=1, j=1 --> 비김, i=2, j=0 --> teamA 승
        for (int i = 0, j = 2; i < 3; i++, j--) {
            if (score[teamA * 3 + i] > 0 && score[teamB * 3 + j] > 0) {
                score[teamA * 3 + i]--;
                score[teamB * 3 + j]--;
                dfs(teamA, teamB + 1, score);
                score[teamA * 3 + i]++;
                score[teamB * 3 + j]++;
            }
        }
        /*
        // teamA가 이기고 teamB가 지는 경우
        if (temp[teamA * 3 + 0] > 0 && temp[teamB * 3 + 2] > 0) {
            temp[teamA * 3 + 0]--;
            temp[teamB * 3 + 2]--;
            dfs(teamA, teamB + 1, temp);
            temp[teamA * 3 + 0]++;
            temp[teamB * 3 + 2]++;
        }
        
        // teamA와 teamB가 비기는 경우
        if (temp[teamA * 3 + 1] > 0 && temp[teamB * 3 + 1] > 0) {
            temp[teamA * 3 + 1]--;
            temp[teamB * 3 + 1]--;
            dfs(teamA, teamB + 1, temp);
            temp[teamA * 3 + 1]++;
            temp[teamB * 3 + 1]++;
        }
        
        if (temp[teamA * 3 + 2] > 0 && temp[teamB * 3 + 0] > 0) {
            // teamA가 지고 teamB가 이기는 경우
            temp[teamA * 3 + 2]--;
            temp[teamB * 3 + 0]--;
            dfs(teamA, teamB + 1, temp);
            temp[teamA * 3 + 2]++;
            temp[teamB * 3 + 0]++;
        }*/
    }

    private static String src = "4 0 0 4 0 1 3 0 2 2 0 3 1 0 4 0 0 4\r\n" +
                                "5 0 0 0 5 0 0 0 5 5 0 0 0 5 0 0 0 5\r\n" +
                                "2 3 0 0 0 5 2 3 0 2 3 0 1 0 4 2 3 0\r\n" +
                                "4 1 0 3 1 1 2 1 2 2 1 2 0 1 4 1 1 3";
}