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

문제 흐름

1. 문제 목표
   • T명이 주어졌을 때, 두 팀으로 나누고 팀 능력치 차이의 최소값을 구하는 문제입니다.
   • 각 팀의 능력치는 해당 팀의 두 사람 사이 능력치 합으로 계산합니다.
   • 두 팀의 능력치 차이가 최소가 되도록 팀을 나누는 것이 핵심입니다.
2. 입력 설명
   • 첫 줄에 사람 수 T가 주어집니다 (항상 짝수).
   • 이후 T x T 크기의 능력치 행렬이 주어지며, 행렬의 (i, j)는 i번과 j번 사람이 같은 팀일 때 기여하는 능력치를 의미합니다.
3. 제약 조건
   • 사람 수가 최대 20명이므로 가능한 팀 조합의 경우의 수는 조합(C(T, T/2))입니다.
   • 완전탐색을 이용해 각 조합을 모두 탐색하면서 최소 능력치 차이를 찾습니다.

 

핵심 아이디어

• 완전 탐색(백트래킹)을 사용해 모든 팀 조합을 탐색합니다.
• 사람들을 두 팀으로 나누고, 각각의 팀 능력치 합을 계산하여 능력치 차이의 최소값을 구합니다.
• 재귀로 T/2명의 팀 조합을 생성하며, 방문 배열(visit)로 어떤 사람이 어느 팀에 속하는지 표시합니다.

 

알고리즘 흐름

1. 모든 조합 탐색:
   • 사람들을 두 팀으로 나누는 가능한 모든 조합을 탐색합니다.
   • 재귀와 백트래킹으로 방문 배열(visit)을 통해 조합을 관리합니다.
2. 팀 능력치 계산:
   • 조합이 완성될 때마다, 방문 배열을 이용해 각 팀의 능력치 합을 계산합니다.
   • 능력치 차이의 최소값을 갱신합니다.
3. 백트래킹:
   • 재귀 호출 후 방문 상태를 초기화해 다른 조합을 탐색합니다.

---

정답은 더보기 클릭

import java.util.*;

public class Main {

    static int min = Integer.MAX_VALUE;  // 최소 능력치 차이 저장
    static int[][] map;  // 능력치 배열
    static int T;  // 사람 수

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

        T = in.nextInt();  // 사람 수 입력
        map = new int[T][T];  // 능력치 배열 초기화
        boolean[] visit = new boolean[T];  // 방문 여부 배열 (팀 구분용)

        // 능력치 입력 받기
        for (int i = 0; i < T; i++) {
            for (int j = 0; j < T; j++) {
                map[i][j] = in.nextInt();  // (i, j)의 능력치 입력
            }
        }

        // 백트래킹으로 팀을 나눔 (T/2명의 팀 조합 생성)
        recursion(visit, T / 2, 0);

        // 최소 능력치 차이 출력
        System.out.println(min);
    }

    // 백트래킹: 팀 조합을 재귀적으로 탐색
    public static void recursion(boolean[] visit, int count, int start) {
        // 모든 조합이 완성되면 능력치 차이 계산
        if (count == 0) {
            diff(visit);  // 두 팀의 능력치 차이 계산
            return;
        }

        // 팀에 포함할 사람 선택 (조합 생성)
        for (int i = start; i < T; i++) {
            if (!visit[i]) {  // 아직 방문하지 않은 사람
                visit[i] = true;  // 해당 사람을 첫 번째 팀에 포함
                recursion(visit, count - 1, i + 1);  // 다음 사람 탐색
                visit[i] = false;  // 백트래킹 (방문 초기화)
            }
        }
    }

    // 두 팀의 능력치 차이 계산
    public static void diff(boolean[] visit) {
        int startSum = 0;  // 첫 번째 팀 능력치 합
        int linkSum = 0;   // 두 번째 팀 능력치 합

        // 모든 사람에 대해 팀 능력치 계산
        for (int i = 0; i < T; i++) {
            for (int j = 0; j < T; j++) {
                if (visit[i] && visit[j]) {
                    startSum += map[i][j];  // 첫 번째 팀의 능력치 합
                } else if (!visit[i] && !visit[j]) {
                    linkSum += map[i][j];  // 두 번째 팀의 능력치 합
                }
            }
        }

        // 최소 능력치 차이 갱신
        min = Math.min(min, Math.abs(startSum - linkSum));
    }
}