14889번 스타트와 링크

단계별로 풀어보기 - 백트래킹- 8단계

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

#include <iostream>
#include <algorithm>
using namespace std;
int N,ans=987654321;
int table[20][20];
bool pick[20];
void dfs(int count,int key)
{
    int sum1=0,sum2=0;
    if(key==N)
    {        
        return;
    }
    
    if(count==N/2)
    {
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(pick[i]==1&&pick[j]==1)
                {
                    sum1+=table[i][j];
                }
                
                if(pick[i]==0&&pick[j]==0)
                {
                    sum2+=table[i][j];
                }
            }
        }
        ans=min(ans,abs(sum1-sum2));
        return;
    }
    pick[key]=1;
    dfs(count+1,key+1);
    
    pick[key]=0;
    dfs(count,key+1);
}

int main()
{
    cin>>N;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            cin>>table[i][j];
        }
    }
    
    dfs(0,0);
    cout<<ans;
    
    return 0;
}