[백준 14889]스타트와 링크

문제는 요기->https://www.acmicpc.net/problem/14889

분류는 dfs!

나의 문제점

:문제를 안푼지 오래되서 dfs로 팀 나누는 조건을 만들생각을 하지못했고!!... 

dfs로 한개의 팀을 만든후에 함수 호출로 나머지 팀을 만들어주려고 하다보니 시간 초과가 났다.

1.벡터를 사용해서 두개의 팀을 분리.

2.dfs의 매개변수로 string 으로가지고 다닐 것!

->나는 매개변수로 안가지고다니고 일차원배열에 집어 넣고 기저조건에서 함수 호출해서 그때 일차원배열을 검사했는데 이부분에서 시간초과가 발생한듯 

#include<iostream>

#include<algorithm>

#include<string>

#include<vector>

using namespace std;

int N; int arr[22][22];

int ans = 999999999;

void func(string length, int s, int l)

{

if (length.size() == N)

{

vector<int>temp1, temp2;

for (int i = 0; i < length.size(); i++)

{

if (length[i] == '1')temp1.push_back(i);

else temp2.push_back(i);

}

int start = 0, link = 0;

for (int i = 0; i < N / 2; i++)

{

for (int j = 0; j < N / 2; j++)

{

if (i != j)

{

start += arr[temp1[i]][temp1[j]];

link += arr[temp2[i]][temp2[j]];

}

}

}

ans = min(ans, abs(start - link));

}

if (s < N / 2)

{

func(length + '1', s + 1, l);

}

if (l < N / 2)

{

func(length + '2', s , l+1);

}

}

int main() {

cin >> N;

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

cin >> arr[i][j];

func("",0,0);

cout << ans << endl;

return 0;

}