백준 14889: 스타트와 링크

C++ 언어를 사용하여 이 문제를 풀이했습니다. N명의 플레이어를 두 팀으로 나누어 각 팀의 능력치 합 차이를 최소화하는 문제입니다.

문제 소개

• 문제 번호: 14889
• 문제명: 스타트와 링크
• 난이도: Silver 1
• 사용 언어: C++
• 실행 시간: 제공되지 않음
• 메모리: 제공되지 않음
• 문제 요약: N명의 플레이어가 있고, N은 짝수이다. 각 플레이어는 두 팀 중 하나에 속해야 하며, 각 팀은 N/2명의 플레이어로 구성되어야 한다. 두 팀의 능력치 합 차이를 최소화하는 방법을 찾아야 한다.

접근 방법

문제를 이해한 결과, N명의 플레이어를 두 팀으로 나누는 모든 가능한 조합을 탐색해야 함을 알았다. N은 최대 20이므로, 모든 경우의 수를 직접 계산하는 것은 시간 복잡도 측면에서 비효율적이다. 따라서 백트래킹(Backtracking) 알고리즘을 사용하여 팀을 나누는 조합을 생성하고, 각 조합에 대한 점수 차이를 계산하여 최소값을 찾는 방식으로 접근했다.

• 사용 알고리즘/자료구조: 백트래킹, 배열

• 선택 이유:

  • 조합 탐색: 두 팀으로 나누는 문제는 결국 N명 중에서 N/2명을 선택하는 조합의 문제와 같다. 백트래킹은 이러한 조합을 효율적으로 생성하는 데 적합하다.
  • 정확성: 모든 가능한 팀 구성 조합을 탐색하므로, 최적의 해를 보장한다.
  • 제한 조건: N의 크기(최대 20)를 고려했을 때, 백트래킹으로 탐색 가능한 수준이다. (20C10의 조합은 약 18만 가지로, 연산량이 감당 가능하다)

풀이 과정

1. 팀 구성: N명의 플레이어를 팀 A와 팀 B로 나누는 과정을 재귀적으로 구현한다. selected 배열을 사용하여 각 플레이어가 팀 A에 속하는지(true) 팀 B에 속하는지(false)를 표시한다.
2. 재귀 탐색: backtrack 함수를 사용하여 플레이어를 팀 A에 포함시키거나 제외시키는 과정을 반복한다. start 매개변수는 이전 선택된 플레이어의 인덱스보다 큰 인덱스부터 탐색하여 중복을 방지한다. dep 매개변수는 현재까지 팀 A에 선택된 플레이어의 수를 나타낸다.
3. 팀 A 완성 조건: dep가 N/2가 되면, 팀 A에 N/2명의 플레이어가 모두 선택된 것이다. 이 시점에서 팀 B에는 나머지 N/2명의 플레이어가 속하게 된다.
4. 점수 계산: calculate 함수를 호출하여 현재 팀 구성에 대한 두 팀의 능력치 합 차이를 계산한다.
   • 각 팀에 속한 두 플레이어 간의 능력치 합을 teamA와 teamB에 각각 더한다.
   • abs(teamA - teamB)를 계산하여 현재 팀 구성의 능력치 차이를 구한다.
   • 전역 변수 answer를 이 능력치 차이와 min 함수를 사용하여 갱신한다.
5. 백트래킹 되돌리기: 한 플레이어를 팀 A에 선택한 후 재귀 호출이 끝나면, 해당 플레이어를 팀 A에서 제외(false)하고 다음 플레이어를 탐색한다. 이는 다음 탐색 경로에서 이전 선택이 영향을 미치지 않도록 하기 위함이다.
6. 결과 출력: 모든 조합 탐색이 완료되면 answer에 저장된 최소 능력치 차이를 출력한다.

코드 설명

#include <iostream>
#include <cmath>
using namespace std;

int N;
int S[20][20];
bool selected[20];  // t: 팀A, f: 팀B. 초기 상태는 전부 f
int answer = 1e9;

// 조합 완성 시 호출. 탐색과 무관한 단순 점수 계산.
void calculate() {
    int teamA = 0;
    int teamB = 0;

    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (selected[i] && selected[j]) // i와 j 모두 팀 A에 속하면
                teamA += S[i][j] + S[j][i]; // 능력치 더함
            if (!selected[i] && !selected[j]) // i와 j 모두 팀 B에 속하면
                teamB += S[i][j] + S[j][i]; // 능력치 더함
        }
    }

    answer = min(answer, abs(teamA - teamB)); // 현재까지의 최소값 갱신
}

// start: 이번 단계에서 선택 시작할 인덱스
//        손으로 조합 쓸 때 "앞 숫자 다음부터" 와 동일
//        중복 방지. 1선택 후 0으로 못 돌아감.
//
// dep: 현재까지 t의 개수 (선택된 인원 수)
//      dep+1을 인자로 넘기는 방식이라 함수 안 dep는 불변.
//      return 후 올라오면 이전 dep 그대로 유지됨.
void backtrack(int start, int dep) {

    // dep == N/2 인 순간 selected에 t가 정확히 N/2개.
    // dep+1을 넘겨받은 시점에 이미 선택 완료 상태이므로 N/2+1 아님.
    if (dep == N / 2) {
        calculate(); // 팀 구성 완료 시 점수 계산
        return;
    }

    for (int i = start; i < N; i++) {

        selected[i] = true;           // f → t. 팀A에 포함.

        backtrack(i + 1, dep + 1);    // 이 호출이 끝날 때까지 다음 i로 못 넘어감.
                                      // 한 분기 전체를 끝내고 나서야 i++ 됨.

        selected[i] = false;          // t → f. 복구.
                                      // 안 하면 다음 경우의 수에서 이전 t가 남아 조합 오염.
    }
    // 손으로 조합 쓰면 (N=8, 4명):
/* 1~8
    1 2 3 45678
    1 2 4 5678
    1 2 5 678
    1 2 6 78
    1 2 7 8 <= 12 끝
    1 3 4 5678
    1 3 5 678
    1 3 6 78
    1 3 7 8 <= 13 끝
    1 4 5 678
    1 4 6 78
    1 4 7 8 <= 14 끝
    1 5 6 78
    1 6 7 8 <= 16 끝. 1로 시작하는 모든 경우 끝
    이제 2로 시작 1로 시작 금지
    2 3 4 5678
    2 3 5 678
    2 3 6 78
    2 3 7 8
    2 4 5 678
    2 4 6 78
    2 4 7 8
    2 5 6 78
    2 5 7 8
    2 6 7 8 <= 2끝
    3 4 5 678
    3 4 6 78
    3 4 7 8
    3 5 6 78
    3 5 7 8
    3 6 7 8
    4 5 6 78
    4 5 7 8
    5 6 7 8
*/
    // 앞 숫자 정해지면 뒤는 항상 그 다음 번호부터 시작.
    // 이게 backtrack(i+1, dep+1) 이고 start의 역할.
    //
    // 대략적인 런타임 흐름 (N=4, 2명):
    // [f f f f]  시작
    // [t' f f f]  selected[0]=true
    // [t t' f f]  selected[1]=true  => dep==2, return
    // [t f' f f]  selected[1]=false (cancel)
    // [t f t' f]  selected[2]=true  => dep==2, return
    // [t f f' f]  selected[2]=false (cancel)
    // [t f f t']  selected[3]=true  => dep==2, return
    // [t f f f']  selected[3]=false (cancel)
    // [f' f f f]  selected[0]=false (cancel)
    // [f t' f f]  selected[1]=true
    // [f t t' f]  selected[2]=true  => dep==2, return
    // [f t f' f]  selected[2]=false (cancel)
    // [f t f t']  selected[3]=true  => dep==2, return
    // [f t f f']  selected[3]=false (cancel)
    // [f f f f]  selected[1]=false (cancel)
    // [f f t' f]  selected[2]=true
    // [f f t t']  selected[3]=true  => dep==2, return
    // [f f f' f']  selected[2]=false, selected[3]=false (cancel)
}

int main() {
    cin >> N; // 플레이어 수 입력

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> S[i][j]; // 능력치 정보 입력

    backtrack(0, 0);  // 전부 f인 상태에서 시작

    cout << answer; // 최소 능력치 차이 출력
}

복잡도 분석

• 시간 복잡도:

  • 팀을 나누는 조합의 수는 N/2명을 선택하는 조합의 수와 같다. 이는 $C(N,N/2)$로 표현된다.
  • 각 조합에 대해 능력치 계산은 $O(N^2)$ 시간이 소요된다.
  • 따라서 전체 시간 복잡도는 $O(C(N,N/2)\times N^2)$ 이다. N=20일 때, $C(20,10)=184756$이며, $184756\times 20^2$는 약 7천만 연산으로, 시간 제한 내에 충분히 실행 가능하다.

• 공간 복잡도:

  • S 배열: $O(N^2)$
  • selected 배열: $O(N)$
  • 재귀 호출 스택: 최대 깊이가 N/2이므로 $O(N)$
  • 따라서 전체 공간 복잡도는 $O(N^2)$이다.

배운 점

이 문제를 통해 백트래킹 알고리즘을 활용하여 조합 탐색 문제를 효과적으로 해결하는 방법을 다시 한번 익힐 수 있었다. 특히, 중복 조합을 방지하기 위해 start 인덱스를 사용하는 방법과, 탐색 후 상태를 복구하여 다른 탐색 경로에 영향을 주지 않도록 하는 백트래킹의 핵심 원리를 체감할 수 있었다. 또한, 조합의 수가 많더라도 문제의 제약 조건을 고려하여 알고리즘을 선택하면 효율적으로 풀 수 있다는 것을 배웠다.