14889번 스타트와 링크

백트래킹 + 브루트 포스 문제이다.

이 문제 풀면서 기억해야 할 것

1. 51번 째 줄과 60번 째 줄 때문에 안 풀리길래 고민 좀 했다.(주석된 부분) 실수 조심

2. 마찬가지로, 73번 째 줄에 i를 pos로 쓰지말자. (pos가 2일 때 i가 6이라면, 백트래킹으로 3이 들어가버린다.)

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int N = 0;
 
int person[21][21] = { 0, };
 
int ans = 987654321;
 
void BackTracking(vector<int> start, int pos)
{
    if (start.size() == N / 2)
    {
        bool used[21] = { false, };
 
        int value[2] = { 0, };
 
        vector<int> link;
 
        int start_size = start.size();
 
        for (int index = 0; index < start_size; index++)
        {
            used[start[index]] = true; 
            // link팀을 구별하기 위해 bool 배열 사용
            // start팀은 true, link팀은 false
        }    
 
        for (int index = 0; index < N; index++)
        {
            if (!used[index]) // start팀이 아니라면
            {
                link.push_back(index);
            }
        }
        
        int link_size = link.size();
 
        for (int i = 0; i < start_size - 1; i++)
        {
            for (int j = i + 1; j < start_size; j++)
            {
                //value[0] += person[start[i]][start[j]];
                value[0] += (person[start[i]][start[j]] + person[start[j]][start[i]]);
            }
        }
        
        for (int i = 0; i < link_size - 1; i++)
        {
            for (int j = i + 1; j < link_size; j++)
            {
                //value[1] += person[link[i]][link[j]];
                value[1] += (person[link[i]][link[j]] + person[link[j]][link[i]]);
            }
        }
 
        ans = min(ans, abs(value[0] - value[1]));
 
        return;
    }
 
    for (int i = pos; i < N; i++)
    {
        start.push_back(i);
        BackTracking(start, i + 1); // not BackTracking(start, pos + 1);
        start.pop_back();
    }
}
 
int main(void)
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &person[i][j]);
        }
    }
 
    vector<int> v;
 
    BackTracking(v, 0);
 
    scanf("%d\n", ans);
 
    return 0;
}