# 백준 : 스타트와 링크 (14889)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_14889_startandlink)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <cmath>
using namespace std;

int N;
int map[21][21];
int team[21];
long long int result = 100000000000;

long long int cal() {
    long long int team1_val = 0;
    long long int team2_val = 0;
    vector <int> team1;
    vector <int> team2;
    for(int i=0; i<N; i++) {
        if(team[i] == 1)    team1.push_back(i);
        else                team2.push_back(i);
    }
    for(int i=0; i<team1.size()-1; i++) {
        for(int j=i+1; j<team1.size(); j++) {
            team1_val += (map[team1[i]][team1[j]] + map[team1[j]][team1[i]]);
            team2_val += (map[team2[i]][team2[j]] + map[team2[j]][team2[i]]);
        }
    }
    return abs(team2_val - team1_val);
}

void DFS(int index, int cnt) {
    if(index >= N) return;
    if(cnt >= N/2) {
        result = min(result, cal());
        return;
    }
    DFS(index + 1, cnt);
    team[index] = 1;
    DFS(index + 1, cnt + 1);
    team[index] = 0;
    //DFS(index + 1, cnt);
}

int main(void)
{
    cin>>N;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) cin>>map[i][j];
    }
    DFS(0,0);
    cout<<result<<endl;
    return 0;
}

풀이

아이디어는 명확하게 세워놓았는데, 사소한 오류 때문에 시간을 많이 잡아먹었다.
백트래킹을 이용했고, 각각의 경우에 대해 벡터를 만들어놓고 해당 벡터 값을 모두 계산하였다.
어차피 순서대로 1,2,3,4가 있을 때
1,2 / 1,3 / 1,4 / 2,3 / 2,4 / 3,4 만 구하면 되므로 여기에 대한 벡터를 다 더해주면 된다.
(사실 윗 부분을 잘못 구현해서 오류가 계속 발생했었다... 샘플은 다 맞던데 왜 그랬을까)