[Algorithm] 백준_14889 스타트와 링크 java

문제

축구를 위해 모인 N명을 스타트, 링크 두 팀으로 나눠야한다. S[i][j] 에는 i번과 j번이 같은 팀에 속했을 때의 능력치가 주어진다.
그래서 팀에 속해지는 능력치는 S[i][j] + s[j][i]이다. 이때 스타트팀과 링크팀의 능력치 차이가 최소가 되는 경우를 출력하면 된다.

풀이

1. 1~N 까지의 수 중에 N/2개를 선별한다.
   백트래킹 사용.
   원래는 123/456과 456/123를 같은 경우로 보는 풀이를 하고싶었으나 그냥 해도 시간초과가 나지 않아서 PASS..

• 선수 번호를 고른 후 team[선수배열] 배열 값을 1로 변경해 선택됨을 선별.
  

2. N/2명을 다 고른 경우는 calc()를 호출해 능력치 합의 최소를 계산한다.

• start[]/ link[] : 팀원 번호를 저장하는 배열
• start_count/ link_count : 팀원 수
• start_sum/ link_sum : 능력치 합

team 배열을 순회하며 값이 1인 경우는 start 배열에 넣어준다.

다 구한 후에는 능력치를 구해 sum에 더했다. 이때 i == j와 같은 경우는 어차피 값이 0이기 때문에 처리하지 않았다.

최소값은 sum 값들의 차의 절대값으로 구했다.

소스 코드

import java.util.Scanner;

public class BOJ_14889 {
    static int[][] capacity;
    static int N;
    static int[] team;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        capacity = new int[N+1][N+1];
        team = new int[N+1];

        for (int i = 1; i < capacity.length; i++) {
            for (int j = 1; j < capacity.length; j++) {
                capacity[i][j] = sc.nextInt();
            }
        }

        matching(1,0);
        System.out.println(min);
    }

    static void calc() {
        int[] start = new int[N / 2]; // 팀원 번호가 들어가는 배열
        int[] link = new int[N / 2];
        int start_count = 0; //팀원 수
        int link_count = 0;
        int start_sum = 0; //능력치의 합
        int link_sum = 0;

        for (int i = 1; i <= N; i++) {
            if (team[i] == 1) {
                start[start_count++] = i;
            } else {
                link[link_count++] = i;
            }
        }

        // i==j일때 값이 0이기 때문에 따로 처리하지 않았음.
        for (int i = 0; i < N / 2; i++) {
            for (int j = i+1; j < N / 2; j++) {
                start_sum += capacity[start[i]][start[j]] + capacity[start[j]][start[i]];
                link_sum += capacity[link[i]][link[j]] + capacity[link[j]][link[i]];
            }
        }

        min = Math.min(min, Math.abs(start_sum - link_sum));
    }

    static void matching(int start, int count) {
        if (count == (N / 2)) {
            calc();
            return;
        }

        for (int i = start; i <= N; i++) {
            team[i] = 1;
            matching(i + 1, count + 1);
            team[i] = 0;
        }
    }
}