[백준/14889] 스타트와 링크(Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/14889
• 분류 : 백트래킹, 브루트포스
• 풀이 시간 : 30분

문제 해설

1. 선수 0 ~ N명 (N은 신기하게 항상 짝수)
2. N / 2 씩 두 팀을 이름
3. 팀별로 모인 사람끼리의 능력치 구함
4. 두 팀의 능력치 차이가 제일 작을때의 값은?

Solution

풀이 접근 방법

1. 팀 구하기 = 차집합 활용(set.removeAll(set2))
2. 능력치 차이 중 제일 최소 = 브루트포스 알고리즘으로 차이 다 구해봐서 비교
3. 팀을 어떻게 뽑아야하는가 = 조합(백트레킹)
4. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합 = 이중 for문으로 모든 선수와의 관계 더할 때 S(i, j)와 S(j, i) 더해줌

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class Main_14889 {
  static int N;
  static int[][] S;
  static int DIFF = Integer.MAX_VALUE;
  static HashSet<Integer> allPlayer;

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

    N = Integer.valueOf(br.readLine());
    S = new int[N][N];
    // 참석한 사람을 모두 집합에 넣음
    allPlayer = new HashSet<Integer>();

    for (int i = 0; i < N; i++) {
      allPlayer.add(i);
      S[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }

    pickTeam(new HashSet<Integer>(), 0, 0);
    bw.write(DIFF + "\n");
    bw.flush();
    bw.close();
  }

  static void pickTeam(HashSet<Integer> startTeam, int current, int pick) {
    if (pick == N / 2) {
      // 전체 인원 - 스타트 팀의 인원
      HashSet<Integer> linkTeam = new HashSet<Integer>(allPlayer);
      // = 차집합 = 링크 팀 인원
      linkTeam.removeAll(startTeam);

      // 각 팀의 능력치 구함
      int startStats = calcTeamStats(startTeam);
      int linkStats = calcTeamStats(linkTeam);

      // 어떤 팀의 능력치가 클지 모르니 차이의 절댓값으로 비교
      DIFF = Math.min(DIFF, (int) Math.abs(startStats - linkStats));

      return;
    }

    // 현재 넣을 값을 가리키고 있는 current가 뽑을 수 있는 범위 안일 때 뽑음
    if (current < N) {
      // 백트레킹 - 현재 사람을 뽑았을 때
      startTeam.add(current);
      pickTeam(startTeam, current + 1, pick + 1);
      // - 뽑지 않고 그냥 넘어갔을 때
      startTeam.remove(current);
      pickTeam(startTeam, current + 1, pick);
    }

  }

  static int calcTeamStats(HashSet<Integer> team) {
    int stats = 0;
    ArrayList<Integer> player = new ArrayList<Integer>(team);

    for (int i = 0; i < player.size() - 1; i++) {
      for (int j = i + 1; j < player.size(); j++) {
        int p1 = player.get(i);
        int p2 = player.get(j);

        stats += S[p1][p2] + S[p2][p1];
      }
    }

    return stats;
  }

}