백준 14889 스타트와 링크 [C]

문제

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

14889번: 스타트와 링크

 

풀이

백트래킹을 통하여 모든 경우의 수를 탐색해보는 브루트포스 알고리즘을 활용하는 문제이다. 스타트팀에 들어갈 인원을 0으로 표시하고, 링크팀에 들어갈 인원을 1로 표시하도록 하자. 0~2^n-1 까지 이진수로 표현한다면 각각의 인원이 스타트팀, 링크팀에 들어갈 모든 경우를 구할 수 있다. 여기서, 주의해야할 점은 문제의 조건에 따라 스타트팀, 링크팀이 각각 n/2명씩까지만 들어갈 수 있도록 처리를 해주는 것이다. 해당 이진수의 경우에 대해, 스타트팀에 대한 sum 과 링크팀에 대한 sum을 구해준 이후에 차이 중 최소값을 출력해주면 된다. 

 

코드

#include <stdio.h>
#include <vector>
#include <math.h>

using namespace std;

int n, path[30], ans = 999999999;
vector<vector<int>> map;

int getSum(int flag) {
    int i, j, sum = 0;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (path[i] == flag && path[j] == flag) {
                sum += map[i][j];
            }
        }
    }
    return sum;
}

void dfs(int depth, int one) {
    int i;
    if (depth == n) {
        int oneSum = getSum(1);
        int zeroSum = getSum(0);
        if (abs(oneSum - zeroSum) < ans) {
            ans = abs(oneSum - zeroSum);
        }
        return;
    }
    // 0
    if (depth - one < n / 2) {
        path[depth] = 0;
        dfs(depth + 1, one);
    }
    // 1
    if (one < n / 2) {
        path[depth] = 1;
        dfs(depth + 1, one + 1);
    }
}

int main() {
    int i, j, a;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        vector<int> imsi;
        for (j = 0; j < n; j++) {
            scanf("%d", &a);
            imsi.push_back(a);
        }
        map.push_back(imsi);
    }

    dfs(0, 0);
    printf("%d", ans);
    return 0;
}