구현 ( 백트래킹 )

백준 6987번 구현 문제를 백트래킹을 이용해 Java로 풀어보았다.
결국 자력으로 풀지 못해서 남의 풀이를 보고 도움을 받아 풀었다. 그래도 시간이 너무 오래 걸려서 찝찝하지만 남의 풀이 그대로 베끼기보다는 참고만 해서 내가 직접 짠 코드를 남기려 한다...

---

백트래킹

백트래킹을 이용해 가능한 모든 경우들과 입력으로 주어진 경기 결과를 대조해서 만약 가능한 경우 중 하나와 일치할 경우 true를 반환하고 아니면 false를 반환하도록 했다.
그런데 내가 짠 코드는 결국 이미 가능하다는 결과가 나오더라도 모든 경우를 다 비교해보고서야 끝나기 때문에 나중에 추가로 이미 해당 test case 가 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씩 추가해가며 마지막에 두 배열이 모두 일치하는지 비교하는 방식이다.

---

아래는 내가 제출한 코드다.

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;
    }
}