[백준] 14889 C++ 스타트와 링크(백트랙킹)

- 문제 설명

 

- 문제 풀이

각 팀의 능력치 합의 최소치는 백트래킹에 익숙하다면 쉽게 구할 수 있지만 두 팀을 중복되지 않게 짜기 위한 최적 방법을 찾아내는게 생각보다 헷갈렸다. 안그러면 계속 시간 초과가 된다.

때문에 재귀함수 인자를 넘겨줄때 pos(다음 값)값 + 1이 아닌 현재 반복값 + 1을 해줘야 된다.

팀은 한 팀만 구하면, 즉 n/2만큼만 구하면 나머지 다른 팀은 정해져 있으므로 depth는 n/2일 때 결과값을 갱신하면 된다.

 

 

- 코드

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

int n;
int S[22][22];
bool visit[12];
int result = -1;
int start[12];
int link[12];

void make_team(int pos, int depth)
{
    if(n/2 == depth) // 절반 인원만 팀을 정해도 나머지 팀은 정해지므로
    {
        int temp1 = 1;
        int temp2 = 1;
        for(int i = 1; i <= n; i++)
        {
            if(visit[i])
            {
                start[temp1] = i;
                temp1++;
            }
            else
            {
                link[temp2] = i;
                temp2++;
            }
        }
        temp1 = 0;
        temp2 = 0;
       for(int i = 1; i <= n/2-1; i++) // 각 팀을 한번에 계산하므로 n/2를 해준다.
       {
           for(int j = i+1; j <= n/2; j++)
           {
               temp1 += S[start[i]][start[j]] + S[start[j]][start[i]];
               temp2 += S[link[i]][link[j]] + S[link[j]][link[i]];
           }
       }
        int temp = abs(temp1 - temp2);
        if(result == -1 || result > temp) // 초기값은 -1이고, 0보다 작은 값은 나오지 않으므로 최적값 갱신
            result = temp;
        
        return;
    }

    
    for(int i = pos; i < n; i++) // i < n인 이유는 반복을 제외하기 위해
    {
        if(!visit[i]) // 방문하지 않았다면
        {
            visit[i] = true;
            make_team(i+1 , depth+1); // i+1 대신 pos+1로 하면 중복 연산이 많아져 시간초과함.
            visit[i] = false;
        }
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            cin >> S[i][j];
        }
    
    make_team(1,0);
    cout << result;
    
    return 0;
}