[BOJ] - 15661. 링크와 스타트 [완전탐색] - c++

https://www.acmicpc.net/problem/15661

DFS+완전탐색 풀이

1.DFS(재귀)로 0~N-1 index를 star팀과 link팀에 나눌 수 있는 모든 경우 확인
2.calc함수에 전달된 벡터에는 index가 나누어져 있어 합 구해서 리턴 가능
ex) [star:0,1,2,3,4,5,6,7 / link: ] => [star:0,1,2,3,4,5,6 / link : 7] => [star: 0,1,2,3,4,5,7 / link:6] ...

using namespace std;
int team[20][20];
int N;
int answer = 2000;

int calc(vector<int> &x)
{   
    int tot=0;
    for(auto a:x)
    {
        for(auto b:x)
        {
            tot+=team[a][b];
        }
    }
    return tot;
}

void dfs(vector<int> &a, vector<int> &b, int idx)
{
    if(idx==N)
    {
        answer=min(answer,abs(calc(a)-calc(b)));
        return;
    }
    a.push_back(idx);
    dfs(a,b,idx+1);
    a.pop_back();
    b.push_back(idx);
    dfs(a,b,idx+1);
    b.pop_back();
}

int main()
{
    cin>>N;
  for(int i=0;i<N;i++)
  {
      for(int j=0;j<N;j++)
      {
          cin>>team[i][j];
      }
  }
  
  vector<int> star,link;
  dfs(star,link,0);
  
  cout<<answer;
  return 0;
}