[Baekjoon] 14889번: 스타트와 링크

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

14889번: 스타트와 링크

문제 설명

N명의 사람들이 짝수로 주어진다. 같은 인원으로 두 팀으로 나누어 축구를 하려 한다. 이때 양 팀의 인원들은 서로의 팀 능력치가 있다. 양 팀의 실력이 비슷해야 게임이 재미있기 때문에 양 팀의 팀 능력치 차이가 가장 적을 때 그 차이를 출력해야 한다.

풀이 방법

DFS로 해결했다. 포인트는 인덱스와 팀원을 구성한 횟수를 파라미터로 넘겨서 종료 조건을 체크하는 것이다. 그리고 종료 후에 다시 방문했던 곳을 false로 바꿔줘야 다른 조합도 구성할 수 있다.

package baekjoon.backtracking;

import java.io.*;

public class BOJ14889 {

    static int N;
    static int min = Integer.MAX_VALUE;
    static int[][] table;
    static boolean[] isVisited;

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            N = Integer.parseInt(br.readLine());
            table = new int[N][N];
            isVisited = new boolean[N];

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

            organize(0, 0);
            System.out.print(min);
        }
    }

    private static void organize(int idx, int cnt) {
        if (cnt == N / 2) {
            diff();
            return;
        }

        for (int i = idx; i < N; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                organize(i + 1, cnt + 1);
                isVisited[i] = false;
            }
        }
    }

    private static void diff() {
        int team_start = 0;
        int team_link = 0;

        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (isVisited[i] == true && isVisited[j] == true) {
                    team_start += table[i][j];
                    team_start += table[j][i];
                }

                else if (isVisited[i] == false && isVisited[j] == false) {
                    team_link += table[i][j];
                    team_link += table[j][i];
                }
            }
        }

        int val = Math.abs(team_start - team_link);

        if (val == 0) {
            System.out.print(val);
            System.exit(0);
        }

        min = Math.min(min, val);
    }
}