[삼성기출]백준14889 - 스타트와링크

import java.io.*;
public class Main14889_스타트와링크 {
	static int N,R;
	static boolean[] visit;
	static int[][] map;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine().trim());
		R = N/2;
		map = new int[N][N];
		visit = new boolean[N];
		String[] input;
		for(int i=0; i<N; i++) {
			input = br.readLine().trim().split(" ");
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(input[j]);
			}
		}
		
		combination(0,0);
		System.out.println(min);
	}
	static int tmp,min = Integer.MAX_VALUE;
	static void combination(int r, int n) {
		if(r == R) {
			tmp = minCal();
			if(tmp < min) min = tmp;
			return;
		}
		for(int i=n; i<N; i++) {
			if(!visit[i]) {
				visit[i] = true;
				combination(r+1, i);
				visit[i] = false;
			}
		}
	}
	static int minCal() {
		int A = 0;
		int B = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(visit[i] && visit[j]) {
					A+=map[i][j];
				}else if(!visit[i] && !visit[j]) {
					B+=map[i][j];
				}
			}
		}
		return Math.abs(A-B);
	}
}