스타트와 링크 문제 / 백트래킹

📌 스타트와 링크 문제

✅ 구현 코드

*전체 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 능력치 계산 메서드
void CalculatePower(const vector<vector<int>>& SIJ, const vector<int>& Team, vector<int>& Partner, int Idx, int& Sum)
{
    if (Partner.size() == 2)
    {
        Sum += SIJ[Partner[0]][Partner[1]];
        Sum += SIJ[Partner[1]][Partner[0]];
        return;
    }

    for (int i = Idx; i < Team.size(); ++i)
    {
        Partner.push_back(Team[i]);

        CalculatePower(SIJ, Team, Partner, i + 1, Sum);

        Partner.pop_back();
    }
}

// A와 B팀 능력치 차이 계산 메서드
int GetPowerGap(const vector<vector<int>>& SIJ, const vector<int>& A_Team, const vector<int>& B_Team)
{
    vector<int> Partner;
    int A_Power = 0;
    int B_Power = 0;
    CalculatePower(SIJ, A_Team, Partner, 0, A_Power);
    CalculatePower(SIJ, B_Team, Partner, 0, B_Power);

    return abs(A_Power - B_Power);
}

void Backtrack(const int& n, const vector<vector<int>>& SIJ,
    vector<int>& A_Team, vector<bool>& Used, int& Min, int Idx, int Cnt)
{
    if (Cnt == n / 2)
    {
        // B_Team 추가
        vector<int> B_Team;
        for (int i = 0; i < n; ++i)
        {
            if (!Used[i]) B_Team.push_back(i);
        }

        // 능력치 차이 계산
        int PowerGap = GetPowerGap(SIJ, A_Team, B_Team);

        // 능력치 차이 최소값 갱신
        Min = min(Min, PowerGap);

        return;
    }

    // idx부터 탐색하여 중복 제거
    for (int i = Idx; i < n; ++i)
    {
        if (Used[i]) continue;
        Used[i] = true;
        A_Team.push_back(i);

        Backtrack(n, SIJ, A_Team, Used, Min, i + 1, Cnt + 1);

        Used[i] = false;
        A_Team.pop_back();
    }
}

void Solution(const int& n, const vector<vector<int>>& SIJ)
{
    vector<int> A_Team;
    vector<bool> used(n, false);
    int Min = 21e8;

    Backtrack(n, SIJ, A_Team, used, Min, 0, 0);

    cout << endl << "정답: " << Min << endl;
}

int main()
{
    // 입력 값 초기화
    int n;
    cin >> n;

    vector<vector<int>> SIJ(n);
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            int t;
            cin >> t;
            SIJ[i].push_back(t);
        }
    }

    // 능력치 차이 최소 값 계산
    Solution(n, SIJ);

    return 0;
}

🔹void Solution(const int& n, const vector<vector<int>>& SIJ)

void Solution(const int& n, const vector<vector<int>>& SIJ)
{
    vector<int> A_Team;
    vector<bool> used(n, false);
    int Min = 21e8;

    Backtrack(n, SIJ, A_Team, used, Min, 0, 0);

    cout << endl << "정답: " << Min << endl;
}

• vector<int> A_Team: A_Team만 인자로 전달하고 B_Team은 Backtrack 함수 내부에서 선언
• vector<bool> Used: A_Team에 들어간 인원 파악
• int Min = 21e8: 능력치 차이 최소 값

 

🔹void Backtrack(const int& n, const vector<vector<int>>& SIJ,
    vector<int>& A_Team, vector<bool>& Used, int& Min, int Idx, int Cnt)

void Backtrack(const int& n, const vector<vector<int>>& SIJ,
    vector<int>& A_Team, vector<bool>& Used, int& Min, int Idx, int Cnt)
{
    if (Cnt == n / 2)
    {
        // B_Team 추가
        vector<int> B_Team;
        for (int i = 0; i < n; ++i)
        {
            if (!Used[i]) B_Team.push_back(i);
        }

        // 능력치 차이 계산
        int PowerGap = GetPowerGap(SIJ, A_Team, B_Team);

        // 능력치 차이 최소값 갱신
        Min = min(Min, PowerGap);

        return;
    }

    // idx부터 탐색하여 중복 제거
    for (int i = Idx; i < n; ++i)
    {
        if (Used[i]) continue;
        Used[i] = true;
        A_Team.push_back(i);

        Backtrack(n, SIJ, A_Team, Used, Min, i + 1, Cnt + 1);

        Used[i] = false;
        A_Team.pop_back();
    }
}

• 루프를 Idx부터 Idx + 1 증가하여 n -1까지 깊이 우선 탐색하며, A_Team에 배정하고 배정된 Idx는 Used에 기록
• (Cnt == n / 2): 전체 인원의 절반이 A_Team에 배정되었다면, 루프를 돌면서 Used에 기록되지 않은 Idx를 B_Team에 배정
• GetPowerGap(): 두 팀의 능력치 차이를 반환
• 능력치 차이 최소 값 갱신

 

🔹int GetPowerGap(const vector<vector<int>>& SIJ, const vector<int>& A_Team, const vector<int>& B_Team)

// A와 B팀 능력치 차이 계산 메서드
int GetPowerGap(const vector<vector<int>>& SIJ, const vector<int>& A_Team, const vector<int>& B_Team)
{
    vector<int> Partner;
    int A_Power = 0;
    int B_Power = 0;
    CalculatePower(SIJ, A_Team, Partner, 0, A_Power);
    CalculatePower(SIJ, B_Team, Partner, 0, B_Power);

    return abs(A_Power - B_Power);
}

• CalculatePower(): 전달 받은 팀의 능력치를 계산해 저장하는 메서드
• 두 팀의 능력치 차이를 절대 값으로 반환

 

🔹void CalculatePower(const vector<vector<int>>& SIJ, const vector<int>& Team, vector<int>& Partner, int Idx, int Cnt, int& Sum)

// 능력치 계산 메서드
void CalculatePower(const vector<vector<int>>& SIJ, const vector<int>& Team, vector<int>& Partner, int Idx, int& Sum)
{
    if (Partner.size() == 2)
    {
        Sum += SIJ[Partner[0]][Partner[1]];
        Sum += SIJ[Partner[1]][Partner[0]];
        return;
    }

    for (int i = Idx; i < Team.size(); ++i)
    {
        Partner.push_back(Team[i]);

        CalculatePower(SIJ, Team, Partner, i + 1, Sum);

        Partner.pop_back();
    }
}

• 앞서 구현했던 Backtrack() 함수에서 Used 체크 여부와 return 조건의 차이만 있음
• Partner 배열에 두 명이 선수가 들어오면 위와 같이 능력치 계산을 하여 Sum에 누적 합산

 

🔔 결과

N 명의 사람들을 두 팀으로 나눌 수 있는 모든 경우에 대한 능력치 계산을 해야하므로 백트래킹(Backtrack 메서드)을 하였고, 나눠진 각 팀의 능력치를 계산하려면 중복되지 않는 모든 짝꿍의 경우를 백트래킹(CalculatePower 메서드)해야 했다.
2중으로 백트래킹 하다보니 설계하는 과정에서 머릿 속이 많이 복잡했던 것 같은데, 막상 구현을 끝마치고 전체 코드를 살펴봤을 때는 이해하는데 어려움이 없었다.
백트래킹 문제를 많이 풀어보면서 가지치기에 대한 설계와 종료 조건을 설계하는 것을 숙달할 필요가 있다고 느꼈다.