[BOJ] 백준 14889- 스타트와링크(JAVA)

조합 2번 사용 : 1. 팀을 N/2 만큼 나누고 그 팀을 2명씩 또 조합해서 나누어줌

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main{
    private static int[][] ability;
    private static int N;
    private static int result;
    private static int[] linkTeam;
    private static int[] arr;
    private static int[] startTeam;
    private static int[] startPair;
    private static int[] linkPair;
    private static int startSumValue;
    private static int linkSumValue;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        ability = new int[N][N];
 
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                ability[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        result = Integer.MAX_VALUE;
        startSumValue = 0;
        linkSumValue = 0;
        arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
 
        linkTeam = new int[N / 2];
        splitTeam(0, 0);
        System.out.println(result);
    }// end of main
 
    public static void splitTeam(int k, int len) {
        if (len == N / 2) {
 
            process();
            if(result > Math.abs(linkSumValue - startSumValue)) {
                result = Math.abs(linkSumValue - startSumValue);
 
            }
            startSumValue =0;
            linkSumValue =0;
            
            return;
        }
 
        for (int i = k; i < arr.length; i++) {
            linkTeam[len] = arr[i];
            splitTeam(i + 1, len + 1);
        }
 
    }
 
    public static void process() {
        boolean[] visited = new boolean[N];
        for (int i = 0; i < linkTeam.length; i++) {
            visited[linkTeam[i]] = true;
        }
        int index = 0;
        startTeam = new int[N/2];
        for (int i = 0; i < visited.length; i++) {
            if(!visited[i]) {
                startTeam[index++] = i;
            }
        }
        
        
        startPair = new int[2];
        linkPair = new int[2];
        splitPair(0,0);    
        
        
    }
    
    public static void splitPair(int k, int len) {
        if(len == 2) {
            result(startPair, linkPair);
            return;
        }
        for (int i = k; i < startTeam.length; i++) {
            startPair[len] =startTeam[i];
            linkPair[len] = linkTeam[i];
            splitPair(i+1, len+1);
        }
    }
 
    private static void result(int[] start, int[] link) {
        for (int i = 0; i < link.length-1; i++) {
            startSumValue += ability[start[i]][start[i+1]] + ability[start[i+1]][start[i]];
            linkSumValue += ability[link[i]][link[i+1]] + ability[link[i+1]][link[i]];
        }
        
        
 
    }
 
}// end of class