15661번: 링크와 스타트

문제

축구를 하기 위해 모인 N명을 스타트 팀과 링크 팀으로 나누려고 합니다. 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 합니다. 사람마다 다른 사람과 같은 팀이 되었을 때 더해지는 능력치 S[i][j]가 주어질 때, 스타트 팀의 능력치와 링크 팀의 능력치 차이를 최소로 하는 프로그램을 작성하는 문제입니다.

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

핵심 차이점: 인원수 제한(N / 2)의 해제

이전 문제인 '스타트와 링크'는 N명 중 정확히 N/2명을 뽑아야 했으므로 매개변수로 depth를 넘겨 조합(Combination)을 구했습니다. 하지만 이번 '링크와 스타트' 문제는 인원수 제한이 없으므로, N명의 사람 각각에 대해 "스타트 팀에 갈 것인가, 링크 팀에 갈 것인가" 하는 2가지 선택지만 부여하여 모든 부분 집합을 구하면 됩니다.

풀이 1: 부분 집합을 구하는 백트래킹 탐색

N명의 사람 각각을 true 팀과 false 팀으로 나누는 방식입니다. 모든 사람의 소속이 정해졌을 때(N명 모두 탐색 완료) 능력치 차이를 계산합니다.

• 상태 전이: 현재 탐색 중인 사람(idx)을 스타트 팀(visited[idx] = true)에 넣고 다음 사람을 탐색(go(idx + 1))합니다. 탐색을 마치고 돌아오면 링크 팀(visited[idx] = false)에 넣고 다음 사람을 탐색(go(idx + 1))합니다.
• 유효성 검사: 모든 사람을 배치했을 때(idx == n), 한 팀에 모든 사람이 몰려있으면(0명 vs N명) 안 됩니다. 이를 방지하기 위해 스타트 팀의 인원을 세고, 1명 이상 N-1명 이하일 때만 능력치를 계산하여 최솟값을 갱신합니다.

코드 1

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

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

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

       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());
          }
       }

       visited = new boolean[n];
       
       // 0번 사람부터 팀 배정 시작
       go(0);

       System.out.println(ans);
    }

    static void go(int idx) {
       // N명 모두 팀 배정이 끝난 경우
       if (idx == n) {
          int sum1 = 0;
          int sum2 = 0;
          
          for (int i = 0; i < n; i++) {
             for (int j = i + 1; j < n; j++) { 
                if (visited[i] && visited[j]) {
                   sum1 += s[i][j] + s[j][i];
                } else if (!visited[i] && !visited[j]) {
                   sum2 += s[i][j] + s[j][i];
                }
             }
          }

          // 최솟값 갱신
          ans = Math.min(ans, Math.abs(sum1 - sum2));
          return;
       }

       // 현재 사람을 스타트 팀(true)에 배정
       visited[idx] = true;
       go(idx + 1);

       // 현재 사람을 링크 팀(false)에 배정
       visited[idx] = false;
       go(idx + 1);
    }
}

풀이 2: 비트마스킹(Bitmasking)을 활용한 완벽한 최적화

비트마스킹을 활용하면, '팀에 적어도 1명 이상이 있어야 한다'는 예외 조건마저 반복문 범위 설정 하나로 완벽하게 해결할 수 있습니다. 메서드 분리를 통해 가독성을 더욱 높였습니다.

• 반복문 범위의 마법: 모든 상태를 나타내는 1 << n의 값 중, 절반인 (1 << n) / 2까지만 탐색합니다. (for (int i = 1; i < (1 << n) / 2; i++))
  • i가 1부터 시작하므로 비트에 최소한 하나의 1이 포함됨이 보장됩니다. (스타트 팀 최소 1명 확보)
  • i가 (1 << n) / 2 - 1 까지만 순회하므로, 가장 앞자리 비트는 무조건 0이 됩니다. (링크 팀 최소 1명 확보)
  • A팀과 B팀이 완전히 뒤바뀌는 대칭 경우의 수도 탐색 절반 축소를 통해 제거되어 속도가 2배 빨라집니다.
• 메서드 분리 (getDiff): 비트 상태 x를 매개변수로 받아 두 팀의 능력치 차이를 반환하는 로직을 분리하여 메인 로직이 훨씬 깔끔해졌습니다.
• 이중 반복문 최적화: getDiff 내부에서 배열을 순회할 때, j = i + 1부터 순회하고 s[i][j] + s[j][i]를 한 번에 더해주면 연산량을 정확히 절반으로 줄일 수 있습니다.

코드 2

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

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

    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());
          }
       }

       // 절반만 탐색해도 모든 팀 분배 조합을 확인할 수 있음
       for (int i = 1; i < (1 << n) / 2; i++) {
          ans = Math.min(ans, getDiff(i));
       }

       bw.write(ans + "");
       bw.flush();
    }

    static int getDiff(int x) {
       int sum1 = 0;
       int sum2 = 0;

       for (int i = 0; i < n; i++) {
          // j를 i + 1부터 시작하여 연산량을 절반으로 최적화
          for (int j = i + 1; j < n; j++) {
             // 둘 다 1번 팀인 경우
             if ((x & (1 << i)) != 0 && (x & (1 << j)) != 0) {
                sum1 += s[i][j] + s[j][i];
             } 
             // 둘 다 0번 팀인 경우
             else if ((x & (1 << i)) == 0 && (x & (1 << j)) == 0) {
                sum2 += s[i][j] + s[j][i];
             }
          }
       }

       return Math.abs(sum1 - sum2);
    }
}

알고리즘 분류

브루트포스 알고리즘 (Brute Force), 백트래킹 (Backtracking), 비트마스킹 (Bitmasking)