[백준][JAVA알고리즘]14889번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int min = Integer.MAX_VALUE;
	static int[][] arr;
	static boolean[] visit;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine()); //사람수
		arr = new int[N][N];  //능력치를 담기 위한 배열
		visit = new boolean[N];
		
		for(int i = 0 ; i < N ; i++) {
		StringTokenizer str = new StringTokenizer(br.readLine());  //능력치
		for(int j = 0 ; str.hasMoreTokens();j++) {
			arr[i][j]= Integer.parseInt(str.nextToken());
		}
		}
		
		dfs(0,0);  //dfs
		
		System.out.println(min);
		

}
	public static void dfs(int depth, int a) {
		
		if(depth == N/2) {  //두팀을 나눌때까지
			diff();
			return;
		}
		
		for(int i = a ; i < N ; i++) {
			visit[i]=true;  
			dfs(depth+1, i+1);
			visit[i]=false;
		}	
	}
	
	public static void diff() {
		int start = 0;
		int link = 0;
		for(int i = 0 ; i < N-1 ; i++) {
			for(int j = i+1 ; j < N ; j++) {
				if(visit[i]==true && visit[j]==true) {  //visit여부로 팀원을 나누고
					start += arr[i][j];  //팀원을 더함
					start += arr[j][i];
				}
				else if(visit[i]==false && visit[j]==false) {
					link += arr[i][j];
					link += arr[j][i];
				}
				
			}
		}
		
		int val = Math.abs(start - link);  //두팀의 능력치를 빼줌
		
		if(val == 0) {  //두팀의 능력치가 0이면 능력치의 차이가 없음으로 바로 출력
			System.out.println(val);
			System.exit(0);
		}
		
		min=Math.min(min,val);  //아니면 능력치의 최소치를 비교하여 출력
	}
	

}

1.dfs 팀원을 나누기 위한 dfs 사용

 

2.팀원을 나누고 방문여부로 팀원의 능력치를 더하고 두팀의 능력치를 빼줌

 

3.두팀의 능력치가 0인경우를 생각하기

 

4.아니면 min으로 두팀의 능력치를 비교하고 가장 작은 능력치 출력