<백준> 14889번 자바 알고리즘

import java.util.*;

public class Main
{   
    static int N;
    static int[][] arr;
    static boolean[] visit;
    static int MIN = Integer.MAX_VALUE;
    
	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        
        arr = new int[N][N];
        visit = new boolean[N];
        
        for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j] = in.nextInt();
			}
		} 
		
		Bp(0, 0);
		System.out.println(MIN);
	}
	
	private static void Bp(int idx, int cnt){
	    if(cnt == N/2){
	        
	        Cal();
	        
	        return;
	    }
	    for(int i = idx; i < N; i++){
	        if(!visit[i]){
	            visit[i] = true;
	            Bp(i + 1, cnt + 1);
	            visit[i] = false;
	        }
	    }
	}
	
	private static void Cal(){
	    int team_s = 0;
	    int team_l = 0;
	    
	    for(int i = 0; i < N - 1; i++){
	        for(int j = i + 1; j < N; j++){
	            if(visit[i] == true && visit[j] == true){
	                team_s += arr[i][j];
	                team_s += arr[j][i];
	            }
	            else if (visit[i] == false && visit[j] == false){
	                team_l += arr[i][j];
	                team_l += arr[j][i];
	            }
	            
	        }
	    }
	    
	    int val = Math.abs(team_s - team_l);
	    
	    if(val == 0){
	        System.out.println(val);
	        System.exit(0);
	    }
	    
	    MIN = Math.min(MIN, val);
	    
	}
}