[백준] C++ 알고리즘 14889번 - 스타트와 링크문제

문제

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

14889번: 스타트와 링크

소스코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n;
int arr[21][21];
int back(int index, vector<int>& first, vector<int>& second) {
    if (index == n+1) {
        if (first.size() != n / 2) return -1;
        if (second.size() != n / 2) return -1;
        int t1 = 0;
        int t2 = 0;
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n / 2; j++) {
                if (i == j) continue;
                t1 += arr[first[i]][first[j]];
                t2 += arr[second[i]][second[j]];
            }
        }
        int diff = abs(t1 - t2);
        return diff;
    }
    int ans = -1;
    first.push_back(index);
    int x=back(index + 1, first, second);
    if (ans == -1 || (x != -1 && x < ans)) {
        ans = x;
    }
    first.pop_back();
    second.push_back(index);
    int y = back(index + 1, first, second);
    if (ans == -1||(y!=-1&&y<ans)) {
        ans = y;
    }
    second.pop_back();
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }
    vector<int> first, second;
    cout << back(1, first, second);
}

해설

1 2 3 4

O O O O 

X X X X

팀을 어디에 선택하느냐에 따라 결과가 달라지므로 전부다해봄으로써 결과값을 도출해낼 수 있다.

이전에 조사했던부분을 다시 빼는것을 백트레킹 기법이라하며, 이런 문제는 백트레킹으로 쉽게 해결할 수 있다.