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

문제

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

14889번: 스타트와 링크

 

코드

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

public class Main {
	
	static int n;
	static int board[][];
	static boolean check[];
	static int min = Integer.MAX_VALUE;
	
	public static void main (String[] args) throws java.lang.Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		
		board = new int[n+1][n+1];
		check = new boolean[n+1];
		
		for(int i=1;i<=n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=n;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		back(1, 0);
		
		System.out.print(min);
		
	}	
	
	static void back(int start, int length) {
		if(length == n/2) {			
			int s = 0;
			int l = 0;
			
			for(int i = 1; i < n; i++) {
				for(int j = i+1; j <= n; j++) {
					if(check[i] && check[j])
						s += board[i][j] + board[j][i];
					else if(!check[i] && !check[j])
						l += board[i][j] + board[j][i];
				}
			}

			min = Math.min(min, Math.abs(s - l));
			return;			
		}
		for(int i=start;i<=n;i++) {
			if(!check[i]) {
				check[i] = true;
				back(i+1, length+1);
				check[i] = false;
			}
		}
		
	}
	
}