백준 14889 : 스타트와 링크 _자바 Java

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

---

import java.io.*;
import java.util.*;

public class Main {
	static int team[][];
	static boolean[]visit;
	static int N,min=Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		team= new int[N][N];
		visit=new boolean[N];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				team[i][j]=sc.nextInt();
			}
		}
		
		bt(0,0);
		System.out.println(min);
	}// main()
	
	static void bt(int a,int depth) {	//팀을 골라줌 
		if(depth==N/2) {
			cal();
			return;
		}
		
		for(int i=a;i<N;i++) {
			if(!visit[i]) {
				visit[i]=true;
				bt(i+1,depth+1);
				visit[i]=false;	
			}
			
		}
	}
	
	static void cal() {		//골라준 팀을 기준으로 틍력치를 더해서 비교
		int aP=0,bP=0;	
		//System.out.println(Arrays.toString(tA)+Arrays.toString(tB));
		for(int i=0;i<N-1;i++) {
			for(int j=i+1;j<N;j++) {
				if(visit[i]==true&&visit[j]==true) {
					aP+=(team[i][j]+team[j][i]);
				}else if(visit[i]==false&&visit[j]==false){
					bP+=(team[i][j]+team[j][i]);
				}
			}
		}
		
		int gap = Math.abs(aP-bP);	//각 팀의 능력치 차이 절댓값		
		min=Math.min(gap, min);		//최솟값을 비교 저장
		
	}//cal()
	
}// class Main