白駿6987号(Java)

38344 ワード
Java algorithm boj Backtracking Implementation simulation インプリメンテーション ついせき テキストリンク

実施（遡及）


バックトラックを利用してJavaで白準6987号の実現問題を解決した.
結局自力更生して、人に難問を解くのを見て、人に問題を解くのを手伝った.時間が長すぎて、ちょっと気分が悪いのですが、他人の草を写すより、参考にしただけなので、自分で作ったコードを残したいのですが・・・

ついせき


backtrackingを使用して、可能なすべての状況と入力された試合結果を比較し、可能な場合、いずれかと一致する場合はtrueまたはfalseを返します.
しかし、私が作成したコードが最終的に可能な結果を得たとしても、すべての場合を比較して、見終わってから終了するので、以降のテスト用例がtrueと判定されていれば、その後の状況の数を比較しないために条件を付けて、かえって時間を増やしてしまいます.なぜか...
static void backTracking(int tc, int round){
        if(result[tc])  return; // 이미 가능한 경우가 있었다면 넘기자
        boolean flag = true;
        if(round==15){ // 15라운드 모두 끝났으면
            if(totalNum!=30){ // 애초에 모든 숫자합이 30도 안되면 바로 false
                flag = false;
                return;
            }
            else{
                for(int team=0; team<6; team++){
                    for(int winLose=0; winLose<3; winLose++){
                        if(matchResultInput[team][winLose]!=possibleMatchResult[team][winLose]) {
                            flag = false;
                            break;
                        }
                    }
                    if(!flag)   break;
                }
            }
            if(flag)    result[tc] = true;
            return;
        }

        int t1 = team1[round];  int t2 = team2[round];

        /** t1이 이기고 t2가 질 경우 */
        possibleMatchResult[t1][0]++;   possibleMatchResult[t2][2]++;   totalNum += 2;
        backTracking(tc, round+1);
        possibleMatchResult[t1][0]--;   possibleMatchResult[t2][2]--;   totalNum -= 2;

        /** t1과 t2가 비길 경우 */
        possibleMatchResult[t1][1]++;   possibleMatchResult[t2][1]++;   totalNum += 2;
        backTracking(tc, round+1);
        possibleMatchResult[t1][1]--;   possibleMatchResult[t2][1]--;   totalNum -= 2;

        /** t1이 지고 t2가 이길 경우 */
        possibleMatchResult[t1][2]++;   possibleMatchResult[t2][0]++;   totalNum += 2;
        backTracking(tc, round+1);
        possibleMatchResult[t1][2]--;   possibleMatchResult[t2][0]--;   totalNum -= 2;
    }
全部で15試合あり、各試合で何番目かのチームが対決し、team1とteam2を事前に発表した.何回戦かによって誰が勝つかを決める.
static int[] team1 = { 0,0,0,0,0,1,1,1,1,2,2,2,3,3,4 };
static int[] team2 = { 1,2,3,4,5,2,3,4,5,3,4,5,4,5,5 };
そうです.
だから各チームが勝ったときに負けたときと引き分けたとき、すべての状況が得られます.
static int[][] matchResultInput = new int[6][3];
static int[][] possibleMatchResult = new int[6][3];
そこで,上記の6チームのWIN,DRAW,LOSEに1つずつ追加し,最後に2つの配列が一致するか否かを比較する.
次は私が提出したコードです.
import java.util.*;
import java.io.*;

public class boj6987 {
    static int[] team1 = { 0,0,0,0,0,1,1,1,1,2,2,2,3,3,4 };
    static int[] team2 = { 1,2,3,4,5,2,3,4,5,3,4,5,4,5,5 };
    static int[][] matchResultInput = new int[6][3];
    static int[][] possibleMatchResult = new int[6][3];
    static boolean[] result = new boolean[4];
    static int totalNum = 0;

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int tc=0; tc<4; tc++){
            StringTokenizer stk = new StringTokenizer(bfr.readLine());
            for(int team=0; team<6; team++){
                for(int winLose=0; winLose<3; winLose++)
                    matchResultInput[team][winLose] = Integer.parseInt(stk.nextToken());
            }
            /** 가능한 경우들을 대조해보자 */
            backTracking(tc, 0);
            if(result[tc])    bfw.write("1 ");
            else    bfw.write("0 ");
            matchResultInput = new int[6][3];   possibleMatchResult = new int[6][3];
        }

        bfw.close();
    }

    static void backTracking(int tc, int round){
        if(result[tc])  return;
        boolean flag = true;
        if(round==15){ // 15라운드 모두 끝났으면
            if(totalNum!=30){ // 애초에 모든 숫자합이 30도 안되면 바로 false
                flag = false;
                return;
            }
            else{
                for(int team=0; team<6; team++){
                    for(int winLose=0; winLose<3; winLose++){
                        if(matchResultInput[team][winLose]!=possibleMatchResult[team][winLose]) {
                            flag = false;
                            break;
                        }
                    }
                    if(!flag)   break;
                }
            }
            if(flag)    result[tc] = true;
            return;
        }

        int t1 = team1[round];  int t2 = team2[round];

        /** t1이 이기고 t2가 질 경우 */
        possibleMatchResult[t1][0]++;   possibleMatchResult[t2][2]++;   totalNum += 2;
        backTracking(tc, round+1);
        possibleMatchResult[t1][0]--;   possibleMatchResult[t2][2]--;   totalNum -= 2;

        /** t1과 t2가 비길 경우 */
        possibleMatchResult[t1][1]++;   possibleMatchResult[t2][1]++;   totalNum += 2;
        backTracking(tc, round+1);
        possibleMatchResult[t1][1]--;   possibleMatchResult[t2][1]--;   totalNum -= 2;

        /** t1이 지고 t2가 이길 경우 */
        possibleMatchResult[t1][2]++;   possibleMatchResult[t2][0]++;   totalNum += 2;
        backTracking(tc, round+1);
        possibleMatchResult[t1][2]--;   possibleMatchResult[t2][0]--;   totalNum -= 2;
    }
}
プログラマーコードテスト高得点Kit Hipより辛い
11ゴングツアーでの演習の解決策