[백준] 14889번 - 스타트와 링크 문제 풀이 및 코드 분석 (Java)

문제 링크

1. 문제 분석

문제 개요

• 총 N명의 사람이 있으며, N은 짝수이다.
• 사람들을 두 팀으로 나누어야 한다. (N/2명씩)
• 능력치 행렬 S[i][j]가 주어지며, i번과 j번 사람이 같은 팀일 때 팀의 능력치에 추가된다.
• 두 팀의 능력치 차이를 최소화하는 팀 구성을 찾아야 한다.

제약 조건

• 4 ≤ N ≤ 20이므로 완전 탐색(브루트포스)이 가능하지만, 효율적인 탐색 방법이 필요함.
• S[i][i] = 0이고, S[i][j] ≠ S[j][i]일 수 있다.
• 팀 구성 조합을 만들고, 각 팀의 능력치를 계산한 후, 차이가 최소인 경우를 찾는다.

2. 해결 방법

1) 조합을 이용한 팀 구성

• N명을 두 개의 그룹(N/2명씩)으로 나누어야 하므로 조합을 활용한다.
• 백트래킹을 이용하여 첫 번째 팀을 구성하고, 남은 인원은 자동으로 두 번째 팀이 된다.

2) 능력치 계산

• 선택된 팀원의 조합을 순회하며 능력치 합계를 구한다.
• 두 팀의 능력치 차이를 구한 후 최소값을 갱신한다.

3) 백트래킹을 통한 최적화

• 이미 선택된 인덱스를 활용하여 나머지 팀을 구하는 방식으로 other 배열을 사용한다.

3. 코드 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

  static int N, ans = Integer.MAX_VALUE;

  static int[] nums;

  static int[][] board;

  private static void init() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    N = Integer.parseInt(br.readLine());

    board = new int[N][N];

    for (int r = 0; r < N; r++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int c = 0; c < N; c++) {
        board[r][c] = Integer.parseInt(st.nextToken());
      }
    }
  }

  private static void comb(int cnt, int start) {
    if (cnt == N / 2) {
      int power1 = 0, power2 = 0;

      for (int i = 0; i < N / 2; i++) {
        for (int j = 0; j < N / 2; j++) {
          power1 += board[nums[i]][nums[j]];
        }
      }

      int[] other = new int[N / 2];
      int idx = 0, cur = 0;
      for (int i = 0; i < N; i++) {
        if (idx < N / 2 && i == nums[idx]) {
          idx++;
        } else {
          other[cur++] = i;
        }
      }

      for (int i = 0; i < N / 2; i++) {
        for (int j = 0; j < N / 2; j++) {
          power2 += board[other[i]][other[j]];
        }
      }

      ans = Math.min(ans, Math.abs(power2 - power1));
      return;
    }

    for (int i = start; i < N; i++) {
      nums[cnt] = i;
      comb(cnt + 1, i + 1);
    }
  }

  public static void main(String[] args) throws Exception {
    init();
    nums = new int[N / 2];
    comb(0, 0);
    System.out.println(ans);
  }
}

4. 코드 분석

1) 초기화 (init())

• BufferedReader를 사용하여 입력을 받는다.
• board 배열에 능력치 정보를 저장한다.

2) 조합을 이용한 팀 구성 (comb())

• cnt는 현재까지 선택한 인원 수, start는 다음 선택 가능한 인덱스.
• N/2명의 선수가 선택되면 두 팀의 능력치를 계산한다.
• 능력치 차이를 구한 후 최소값을 갱신한다.
• 백트래킹을 사용하여 탐색을 줄인다.

3) 능력치 계산

• nums를 이용하여 선택된 팀원을 추적한다.
• other 배열을 활용하여 남은 팀원을 구성하고 능력치를 계산한다.

5. 개선할 점 및 대체 방법

1) other 배열 최적화

• 기존에는 other 배열을 만들고 인덱스를 관리했지만, 이를 더욱 효율적으로 구성할 방법을 고민해볼 수 있음.

2) 완전 탐색의 시간 복잡도 줄이기

• N이 20이므로 최대 10C5 = 252개의 조합을 탐색해야 하지만 백트래킹을 이용하여 불필요한 연산을 줄였다.

3) 대체 방법

• 비트마스킹을 활용한 방법: N ≤ 20이므로 비트마스킹을 활용하면 더 효율적인 탐색이 가능하다.
• 동적 계획법(DP) 활용: dp[state]를 이용해 부분 문제를 저장하면 중복 계산을 줄일 수 있다.