백준 15661 링크와 스타트 (C++)

15661번: 링크와 스타트

백트래킹을 이용한 문제이다. 기존 백트래킹과 비슷하게 진행이 된다. 다른 점이라면 result를 구하는 조건이다. 만약 N=4일 때 check에 저장될 수 있는 기록 중 1 0 0 0과 0 1 1 1은 같은 결과를 리턴하게 된다. 그렇기에 N/2 이하일 경우까지만 모두 스코어 차이를 구해 가장 작은 값을 찾아 저장해주었다. 어렵지 않게 풀 수 있었던 문제였다. 백트래킹 방식에 대해 다시 한번 상기시킬 수 있어 좋은 문제였다.

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int N, result = 987654321;
int A[20][20];
bool check[20];

int scoreDif() {
    int score1 = 0, score2 = 0;

    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (check[i] && check[j]) {
                score1 += A[i][j] + A[j][i];
            }
            else if(!check[i] && !check[j]){
                score2 += A[i][j] + A[j][i];
            }
        }
    }

    return abs(score1 - score2);
}

void dfs(int depth, int n) {
    if (n >= 1 && n <= N / 2) {
        result = min(result, scoreDif());
    }

    for (int i = depth; i < N; i++) {
        check[i] = true;
        dfs(i + 1, n + 1);
        check[i] = false;
    }
}

void solution() {
    dfs(0, 0);
    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    solution();

    return 0;
}