[백준] 14889 : 스타트와 링크 - JAVA(자바) - 사좋배 공유

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

14889번: 스타트와 링크

public class Main {
	static int[][] arr;
	static ArrayList<Integer> list;
	static int size;
	static int MIN;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		size = sc.nextInt();
		arr = new int[size + 1][size + 1];
		MIN=Integer.MAX_VALUE;
		list = new ArrayList<Integer>();
		for (int i = 1; i <= size; i++) {
			for (int j = 1; j <= size; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		dfs(1);
		System.out.println(MIN);
	}

	private static void dfs(int index) {
		if (list.size() == size / 2) {
			int[][] visited= new int[size + 1][size + 1];
			int result= solve(visited);
			if(MIN > result) {
				MIN=result;
			}
		}
		for (int i = index; i <= size; i++) {
			list.add(i);
			dfs(i + 1);
			list.remove(list.size() - 1);
		}
	}

	private static int solve(int[][]arr2) {
		int startteam=0;
		int linkteam=0;
		for(int i=0;i<list.size();i++) {
			int number=list.get(i);
			for(int j=1;j<=size;j++) {
				if(number==j) {
					arr2[number][j]=0;
				}
				else {
					arr2[number][j]++;
				}
			}
			for(int k=1;k<=size;k++) {
				if(number==k) {
					arr2[k][number]=0;
				}
				else {
				arr2[k][number]++;
				}
			}
		}

		for(int i=1;i<=size;i++) {
			for(int j=1;j<=size;j++) {
				if(i==j) {
					continue;
				}
				if(arr2[i][j]==2) {
					startteam=startteam+arr[i][j];
					continue;
				}
				if(arr2[i][j]==0) {
					linkteam = linkteam+arr[i][j];
				}
			}
		}
		int result= Math.abs(startteam-linkteam);
		return result;
	}
}