BOJ - 스타트와 링크(14889)

실버3 : dfs 문제이다.

생각

기본적인 dfs 문제이다. 반으로 나눈 팀에 대한 점수를 더하는 것이므로, true false를 통해 구현할 수 있다.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int N;
int map[21][21];
bool check[21];
int ans = 987654321;
 
void go(int count, int start){
    if (count == N/2) {
        int start, link;
        start = link = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (check[i] && check[j]) start += map[i][j];
                if (!check[i] && !check[j]) link += map[i][j];
            }
        }
        ans = min(ans, abs(start-link));
        return;
    }
    for (int i = start; i <= N-(N/2)+count+1; i++) {
        check[i] = true;
        go(count+1, i+1);
        check[i] = false;
    }
}
 
int main(){
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }
    go(0, 1);
    cout << ans << '\n';
}
 

Reference

• 백준(14889번) - 스타트와 링크