정답코드

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

public class Main {
    static int N;
    static boolean[] visited;
    static int[][] team;
    static int difference = 10000000;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        visited = new boolean[N];
        team = new int[N][N];
				
		//input 처리하는 부분
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine());
            for (int j = 0; j < N; j++) {
                team[i][j] = Integer.parseInt(st.nextToken());
            }
        }
				
		//DFS 시작
        compute(0,0);
        System.out.println(difference);
        System.exit(0);
    }

    public static void compute(int idx,int depth) {
				
       //절반만 팀1에 담으면 자동으로 팀2는 결정된다 -> depth = N으로 하면 시간초과 
        if (depth == N / 2 )  {
      		//팀이 정해지면 팀1, 팀2 사이 능력치 계산 true는 1팀 false는 2팀
			check_ability();
            return;
        }
				/*
				8명 4번 DFS -> i번째 depth마다 확인 
				1,2,3,4 
				
				[1]  [2~8]
				[2]   [1 3~8]
				[6,7,8] [1,2,3,4,5]	

				[1,2,3,4] [5,6,7,8]
				
				[1,2,3,4,5]
				*/

        for (int i = idx; i < N; i++){
            if(visited[i] == false) {
                //현재 추가하는 사람 체크
				visited[i] = true;
				//(다음 사람,다음 레벨)로 DFS 
                compute(idx + 1, depth + 1);
                //바꿔줬던 visited DFS 끝나고 나서 다시 복구해주기
				visited[i] = false;
            }
        }
    }

    public static void check_ability() {
        int ability1 = 0;
        int ability2 = 0;
				
        for(int i = 0; i < N-1;i++){
            for(int j = i+1; j < N; j++){
                if(visited[i]==true && visited[j]==true){
                    ability1 += (team[i][j] + team[j][i]);
                }
                else if(visited[i]==false && visited[j]==false){
                    ability2 += (team[i][j] + team[j][i]);
                }
            }
        }

        difference = Math.min(Math.abs(ability1-ability2),difference);

        if (difference == 0) {
            System.out.println(difference);
            System.exit(0);
        }
    }
}

전략

• 특정 팀원이 team1에 참여하는 경우와 참여하지 않는 경우로 나눠서 DFS를 돌린다.

• 조합과 관련된 문제 tip: 특정 팀원이 team1에 참여하는 것과 team2에 참여하는 경우의 수 (멤버 구성은 같고 팀명만 다른 경우를 고려할 필요가 없다)

• DFS를 N까지 다 돌릴 필요가 없고 N/2까지만 돌리면 된다

팁

• 2분할 되는 문제는 일일이 멤버를 받아서 ArrayList나 자료구조에 저장하는 거 보다 boolean 배열을 이용해서 true, false로 판별하자