BOJ14889 : 스타트와 링크 (Silver 3)

#include <iostream>
using namespace std;

int N;
int map[21][21];
int ans = 100000000;
bool is_visited[21];

void DFS(int player, int cnt)
{
    if (cnt == N / 2)
    {
        int score1 = 0;
        int score2 = 0;
        for (int i = 1; i <= N; i++)
        {
            for (int j = i + 1; j <= N; j++)
            {
                if (is_visited[i] && is_visited[j])
                {
                    score1 += map[i][j];
                    score1 += map[j][i];
                }
                else if (!is_visited[i] && !is_visited[j])
                {
                    score2 += map[i][j];
                    score2 += map[j][i];
                }
            }
        }
        ans = min(ans, abs(score1 - score2));

        return;
    }
    for (int i = player + 1; i <= N; i++)
    {
        if (!is_visited[i])
        {
            is_visited[i] = true;
            DFS(i, cnt + 1);
            is_visited[i] = false;
        }
    }
}

int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> map[i][j];
        }
    }
    DFS(0, 0);
    cout << ans;
}

난 아직도 백트래킹이 너무 어렵다..........  DFS 안한지 너무 오래돼서 코드 어케 짜는지 다 까먹었다... 

더 이해 필요함..

대충 모든 선수들을 Backtracking으로 visit을 1/0 바꿔 가면서 모든 경우의 수 별로 score 차이를 구하고, min 을 update해줌