[백준] 14889번 : 스타트와 링크 - JAVA [자바]

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

dfs 알고리즘 문제이다.

N 명에서 N / 2 명을 뽑는 문제라고 생각하면 된다.

일단 종료 시점은 위에 말한대로 N / 2 명을 teamA(첫번째 팀)으로 뽑았을 때로 하였다.

그리고 종료 시점에 teamA에 속하지 못한 사람들로 teamB를 꾸렸다.
그 다음 각 팀의 능력 합의 차를 구한 뒤 Math.min(MIN, teamA-teamB)을 하여 현재 최솟값과 비교하여 업데이트한다.

팀의 조합에서 (1,2,3) 과 (1,3,2)은 완전히 같은 것이다.

어차피 사람은 0부터 N-1 까지 총 N 명의 사람이 순서대로 (0, 1, 2, ,,, , N-1) 있다.

그러므로 만약에 i 번째 사람을 뽑았으면 그 다음으로 뽑을 사람은 i + 1 번째 사람부터 보면 된다.

public class bj14889 {

    public static int N;
    public static int MIN;
    public static int[] teamA;
    public static boolean[] visited;
    public static int[][] ability;

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        ability = new int[N][N];
        visited = new boolean[N];
        teamA = new int[N / 2];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            String[] split = line.split(" ");
            for (int j = 0; j < N; j++) {
                int score = Integer.parseInt(split[j]);
                ability[i][j] = score;
                MIN += score;
            }
        }

        dfs(0, 0);

        bw.write(MIN + "");

        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int depth, int index) {
    	// teamA에 N/2 명의 사람을 다 뽑았으면 종료한다.
        if (depth == N / 2) {
        	// teamA에 속하지 못한 번호들로 teamB를 구한다.
            List<Integer> teamBList = new ArrayList<>();
            for (int i = 0; i < N; i++) {
            	// visited[i] == false 이면 선택받지 못한 것이다.
                if (!visited[i]) {
                    teamBList.add(i);
                }
            }
            Object[] teamB = teamBList.toArray();
            
            // 각 팀의 능력합을 구한다.
            int sumA = 0;
            int sumB = 0;
            for (int i = 0; i < N / 2; i++) {
                for (int j = 0; j < N / 2; j++) {
                    sumA += ability[teamA[i]][teamA[j]];
                }
            }
            for (int i = 0; i < N / 2; i++) {
                for (int j = 0; j < N / 2; j++) {
                    sumB += ability[(int) teamB[i]][(int) teamB[j]];
                }
            }
            // 현재 최솟값과 각 팀의 능력 합의 차를 비교하여 업데이트 한다.
            MIN = Math.min(MIN, Math.abs(sumA - sumB));
            return;
        }
        // N-1 번재 사람까지 반복문을 돌면서 뽑는다.
        for (int i = index; i < N; i++) {
        	// 뽑은 사람이 아니면
            if (!visited[i]) {
            	// 뽑고
                visited[i] = true;
                // teamA의 depth(몇번째 사람인지)에 추가한다.
                teamA[depth] = i;
                // 다음 사람을 뽑으러 간다
                // 이때 i + 1 번째 이후로 보기 위해 index 에 i + 1 을 넘겨준다.
                // 몇번째(depth)도 +1을 해서 넘겨준다.
                dfs(depth + 1, i + 1);
                // i 번째 사람을 뽑았을 때의 조합을 다 구했으면
                // 이제 i번째 사람을 안뽑은걸로 초기화하고 
                // 다음 i++ 번째 사람을 뽑는 조합을 구하러 간다.
                visited[i] = false;
            }
        }
    }
}