[BF, DFS] SWEA4012 요리사

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH&categoryId=AWIeUtVakTMDFAVH&categoryType=CODE&&&

 

Solution

• Brute Force로 모든 경우를 다 해본다.
• N개 중 N/2 개를 골라 A로 하고 너미지를 B로 한다.
• 가능한 조합(Combination)을 순회하며 A-B의 절대값의 최솟값을 찾는다.

Point

• next_permutation 함수를 사용해서 조합을 만들어서 사용한다.
• 전체 개수 N 중 조합으로 뽑고자 하는 개수 M개 만큼 1을 넣고 나머지를 0으로 하여 순열을 돌리면, 중복이 제거되어 결과가 나오는데, 이를 배열의 index로 쓰면 조합을 뽑아낼 수 있다.
• 그룹 A, B순서 상관 없으므로 전체 조합 경우의 수 중에 앞의 절반과 뒤의 절반은 같은 결과이기 때문에 뒤의 절반에 해당하는 nCr/2를 버린다.
• 단순 순열을 사용하면 시간 초과가 뜨는데, 차라리 DFS로 푸는 게 사실 더 효율적이다.

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int s[16][16] = { 0 };
vector<int> v(16), id(16);

void printAB(vector<int> &a, vector<int> &b) {
    cout << "A:";
    for (int i = 0; i < N / 2; i++)
        cout << a[i] << " ";

    cout << "    B:";
    for (int i = 0; i < N / 2; i++)
        cout << b[i] << " ";
    cout << endl;
}

void input() {
    cin >> N;
    for (int i = 0; i < N; i++)
        v[i] = i;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> s[i][j];
    for (int i = 0; i < N / 2; i++)
        id[i] = 1;
    for (int i = N / 2; i < N; i++)
        id[i] = 0;
}

int cal(vector<int> &vl) {
    int sum = 0;
    for (int i = 0; i < N / 2 - 1; i++)
        for (int j = i + 1; j < N / 2; j++)
            sum = sum + s[vl[i]][vl[j]] + s[vl[j]][vl[i]];
    return sum;
}

int numComb() {
    int num = 1;
    for (int i = N; 0 < i; i--) {
        if (i > N / 2)
            num *= i;
        else
            num /= i;
    }
    return num / 2;
}

int main() {
    int test_case, T;
    freopen("input.txt", "r", stdin);
    cin >> T;

    for (test_case = 1; test_case <= T; ++test_case) {
        int ans = 987654321, count = 0;

        input();

        int maxCount = numComb();

        //next_permutation 전에 반드시 sort 하고 시작
        sort(id.begin(), id.begin() + N);

        do {
            vector<int> a, b;
            int a_val = 0, b_val = 0, diff = 0;

            //get combination with id[]
            for (int i = 0; i < N; i++) {
                if (id[i])
                    a.push_back(v[i]);
                else
                    b.push_back(v[i]);
            }

            printAB(a, b);

            a_val = cal(a);
            b_val = cal(b);

            diff = abs(a_val - b_val);
            ans = min(diff, ans);

            if (++count == maxCount)
                break;
        } while (next_permutation(id.begin(), id.begin() + N));

        cout << "#" << test_case << " " << ans << endl;
    }
    return 0;
}