14889_스타트와 링크 (JAVA)

14889번: 스타트와 링크

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int num;
    static int[][] ability; //능력치 저장되어있는 배열
    static boolean[] checkTeam; //방문 배열 -> true:스타트팀, false:링크팀으로 사용
    static int ans = Integer.MAX_VALUE; //최소값이므로 integer최대값으로 설정

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        num = Integer.parseInt(br.readLine());
        ability = new int[num][num];
        checkTeam = new boolean[num];

        for(int i=0; i<num; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<num; j++){
                ability[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        makeTeam(0,0); //index=0부터 '두 팀으로 나누기 위한' 탐색 시작

        System.out.println(ans);
    }

    private static void makeTeam(int idx, int cnt){
    
    /*
      1~num의 사람들을 두 팀으로 나누는 함수
      idx : idx번째 사람을 의미, cnt : 스타트팀의 인원
      
      checkTeam[] 배열은 사람들의 팀을 확인했나/안했나를 표시함과 동시에
      true=스타트팀, false=링크팀으로 표시 하는 배열이다.
      
      int idx를 기준으로 이전 인덱스는 확인하지 않고, idx~num의 사람들만 체크한다.
      ( (1,2)와 (2,1)를 같은 것으로 보기 때문에, 이전 인덱스는 확인X)
      
      그러므로 idx~num까지 사람들의 checkTeam[]=false이면,
      아직 무슨 팀인지 확인하지 않았다는 의미이기 때문에 T/F로 재귀를 돌린다.
      이때 checkTeam[]=true=스타트팀 이면, 스타트팀의 cnt를 +1해준다.
      (두 팀의 인원을 각각 num/2명으로 만들어야하기 때문에 스타트팀 입장에서만 보아도 된다.)
      
      cnt==num/2 가 되면, 두 팀이 모두 num/2명이 되었으므로
      각 팀의 능력치 합에 대한 차이를 구한다. -> calDiff()함수
    */
      
        if(cnt == num/2){
            ans = Math.min(ans, calDiff());
            return;
        }

        for(int i=idx; i<num; i++){
            if(!checkTeam[i]){
                checkTeam[i] = true;
                makeTeam(i+1, cnt+1);
                checkTeam[i] = false;
            }
        }
    }

    private static int calDiff(){
        int teamA=0; //스타트팀 능력치 합
        int teamB=0; //링크팀 능력치 합

        for(int i=0; i<num-1; i++){
            for(int j=i+1; j<num; j++) {
            //(i,j)일때 계산 순서: (1,2)(1,3)(1,4)->(2,3)(2,4)->(3,4)
            
                if (checkTeam[i] && checkTeam[j]) //스타트팀이면
                    teamA += ability[i][j] + ability[j][i];
                else if (!checkTeam[i] && !checkTeam[j]) //링크팀이면
                    teamB += ability[i][j] + ability[j][i];
            }
        }

        return Math.abs(teamA-teamB);
    }
}