[백준/C,C++] 14889번: 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

백준 단계별로 풀어보기 백트래킹 마지막 문제입니다.

void dfs(int cnt, int number)
{
    if (cnt == N / 2) {
        synergy();
        return;
    }
    for (int i = number; i < N; i++) {
        M[i] = true;
        dfs(cnt + 1, i + 1);
        M[i] = false;
    }
}

파라미터로 cnt와 number를 받아오는데 number를 받아오는 이유는 1, 2번이 팀인 경우와 2, 1번이 팀인 경우는 점수가 같기 때문에, 번호가 오름차순인 경우만 고려하기 위함입니다. 팀이 2개밖에 없기 때문에 불리언 배열을 이용해 M[i]가 true인 경우 1팀, false인 경우 2팀으로 생각하고 문제를 풀었습니다.

void synergy()
{
    int team1 = 0;
    int team2 = 0;
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N; j++) {
            if (M[i] && M[i] == M[j]) team1 += S[i][j];
            else if (!M[i] && M[i] == M[j]) team2 += S[i][j];
        }
    }
    if (abs(team1 - team2) < res) {
        res = abs(team1 - team2);
    }
}

시너지 점수를 구하는 함수입니다. 1팀 멤버와 2팀 멤버의 시너지 총합을 구하고 그 차를 이전 값과 비교해 계속 갱신해 줍니다.

#include<iostream>

using namespace std;

#define SIZE 21

int S[SIZE][SIZE];
int N;
bool M[SIZE];
int res = 1000000000;

void synergy()
{
    int team1 = 0;
    int team2 = 0;
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N; j++) {
            if (M[i] && M[i] == M[j]) team1 += S[i][j];
            else if (!M[i] && M[i] == M[j]) team2 += S[i][j];
        }
    }
    if (abs(team1 - team2) < res) {
        res = abs(team1 - team2);
    }
}

void dfs(int cnt, int number)
{
    if (cnt == N / 2) {
        synergy();
        return;
    }
    for (int i = number; i < N; i++) {
        M[i] = true;
        dfs(cnt + 1, i + 1);
        M[i] = false;
    }
}

int main(void)
{
    cin >> N;
    N++;

    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N; j++) {
            cin >> S[i][j];
        }
    }
    
    M[1] = true;
    dfs(1, 2);

    cout << res;
    
    return 0;
}

전체 코드를 보면 M[1]은 1팀으로 고정해두고 코드를 짰는데 그 이유는 멤버1을 1팀으로 고정시켜도 전체 경우의 수가 같기 때문입니다. 4명의 팀원이 있다고 가정하면 1, 2 vs 3, 4 또는 1, 3 vs 2, 4 또는 1, 4 vs 2, 3 총 경우의 수가 3가지 나오는데 멤버1은 모두 1팀이어도 됩니다.