백준[14889] 스타트와 링크

삼성 SW역량테스트 문제이다.

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

DFS조합 문제이다. 가능한 조합으로 팀을 만들어 만든 두 팀의 차가 최소가 되는 값을 구하는 문제이다.

이때까지 해왔던 DFS조합으로 팀을 선별하여 두 팀의 합을 구하고 차이를 구하면 되지만, 한가지 유의할 점이 있다.

N=4 이며 4개의 팀이 있다고 가정하자.

 

visit배열을 통해 방문체크를 하며 조합을 두 팀으로 구성할때, 나올 수 있는 경우는

0 0 1 1

0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

여기서 알 수 있는 것은 '0 0 1 1' 경우나 '1 1 0 0' 경우가 같다는 것에 주의해야 한다. 이것에 유의하며 탐색을 진행해야한다.

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<stack>
#include<queue>
 
using namespace std;
 
int n, arr[21][21], visit[21],ans[6],k=1,ans2[6],k2=1,aaa,bbb=987654321;
 
int cal(int a[]) {
    int ss = 0;
    int len = n / 2;
    for (int i = 1; i <= len; i++) {
        for (int j = i+1; j <= len; j++) {
            ss += arr[a[i]][a[j]];
            ss += arr[a[j]][a[i]];
        }
    }
    return ss;
}
 
void dfs(int a,int b) {
    if (b == n / 2) {
        for (int i = 1; i <= n; i++) {
            if (visit[i] == 1) {
                ans[k] = i;
                k++;
            }
            else {
                ans2[k2] = i;
                k2++;
            }
        }
        int s = cal(ans);
        int l = cal(ans2);
        aaa = abs(s - l);
        bbb = min(bbb, aaa);
        
    }
    k = k2 = 1;
    
    for (int i = a; i <= n; i++) {
            visit[i] = 1;
            if (visit[1] == 0) return;
            dfs(i + 1,b+1);
            visit[i] = 0;
    }
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    dfs(1,0);
    printf("%d", bbb);
    return 0;
}