14889번: 스타트와 링크

문제

축구를 하기 위해 모인 N명(짝수)을 N/2명씩 스타트 팀과 링크 팀으로 나누려고 합니다. 사람마다 다른 사람과 같은 팀이 되었을 때 더해지는 능력치 S[i][j]가 주어집니다. 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 N (4 ≤ N ≤ 20, N은 짝수)이 주어집니다. 둘째 줄부터 N개의 줄에 능력치 배열 S가 주어집니다.
• 출력: 첫째 줄에 스타트 팀과 링크 팀의 능력치 차이의 최솟값을 출력합니다.

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

풀이 1: HashSet을 활용한 백트래킹

Set<Integer>를 사용하여 스타트 팀에 속할 인원을 선택하는 완전탐색 풀이입니다.

• 팀원 선택: go 함수에서 반복문을 통해 idx부터 n-1까지 순회하며 HashSet에 인덱스를 추가하고 재귀 호출을 수행합니다. 이후 다음 탐색을 위해 remove로 원상 복구(백트래킹)합니다.
• 능력치 계산: 선택된 팀원이 정확히 n / 2명이 되면 기저 조건(Base Case)에 도달합니다. 이중 반복문을 돌며 두 인덱스 i와 j가 모두 Set에 포함되어 있다면 스타트 팀의 능력치(sum1)에 더합니다. 둘 다 포함되어 있지 않다면 링크 팀의 능력치(sum2)에 더합니다.
• 최솟값 갱신: 두 팀의 능력치 차이의 절댓값을 구하고, 기존의 ans와 비교하여 더 작은 값으로 갱신합니다.

코드 1

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

public class Main {
    static int n;
    static int[][] s;
    static int ans = Integer.MAX_VALUE;

    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.parseInt(br.readLine());
       s = new int[n][n];
       for (int i = 0; i < n; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          for (int j = 0; j < n; j++) {
             s[i][j] = Integer.parseInt(st.nextToken());
          }
       }

       go(0, new HashSet<>());

       bw.write(ans + "");

       bw.flush();
    }

    static void go(int idx, Set<Integer> set) {
       if (set.size() == n / 2) {
          int sum1 = 0;
          int sum2 = 0;
          for (int i = 0; i < n; i++) {
             for (int j = 0; j < n; j++) {
                if (set.contains(i) && set.contains(j)) {
                   sum1 += s[i][j];
                } else if (!set.contains(i) && !set.contains(j)) {
                   sum2 += s[i][j];
                }
             }
          }

          ans = Math.min(ans, Math.abs(sum1 - sum2));

          return;
       }

       for (int i = idx; i < n; i++) {
          set.add(i);
          go(i + 1, set);
          set.remove(i); // 백트래킹
       }
    }
}

풀이 2: 비트마스킹 (Bitmasking)

0부터 (1 << n) - 1까지의 모든 수를 반복문으로 순회하며 부분 집합을 판별하는 방법입니다.

• 전체 상태 순회: 1 << n은 2^n을 의미하며, 0부터 (1 << n) - 1까지의 정수는 각각 N명의 포함 상태를 이진수로 나타낸 고유한 값이 됩니다.
• 팀 배분 조건 확인: 정수값의 이진수 표현에서 1의 개수가 곧 스타트 팀의 인원수가 됩니다. 자바의 Integer.bitCount(i)를 사용하여 1의 개수가 정확히 n / 2개인 상태일 때만 능력치 계산을 수행합니다.
• 팀 포함 여부 판별: 해당 상태 i에 대해 (i & (1 << r)) != 0 연산을 통해 r번째 사람이 스타트 팀인지 링크 팀인지 판별합니다.

이 방식은 백트래킹과 상태 원상 복구 로직이 필요 없어 코드가 매우 간결하며 속도도 빠릅니다.

코드 2

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

public class Main {
    static int n;
    static int[][] s;
    static int ans = Integer.MAX_VALUE;

    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.parseInt(br.readLine());
       s = new int[n][n];
       for (int i = 0; i < n; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          for (int j = 0; j < n; j++) {
             s[i][j] = Integer.parseInt(st.nextToken());
          }
       }

       int totalCases = 1 << n; // 2^n 가지의 경우의 수

       // 0부터 2^n - 1 까지 모든 상태 탐색
       for (int i = 0; i < totalCases; i++) {
          // 비트에서 1의 개수가 정확히 n / 2 (즉, 스타트 팀이 절반인 경우)
          if (Integer.bitCount(i) == n / 2) {
             int sum1 = 0;
             int sum2 = 0;

             for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                   // 비트 연산을 통해 r과 c가 선택된 팀인지 확인
                   boolean hasR = (i & (1 << r)) != 0;
                   boolean hasC = (i & (1 << c)) != 0;
                   
                   if (hasR && hasC) {
                      sum1 += s[r][c];
                   } else if (!hasR && !hasC) {
                      sum2 += s[r][c];
                   }
                }
             }

             ans = Math.min(ans, Math.abs(sum1 - sum2));
          }
       }

       bw.write(ans + "");

       bw.flush();
    }
}

알고리즘 분류

브루트포스 알고리즘 (완전탐색), 백트래킹 (Backtracking), 비트마스킹 (Bitmasking)