[BOJ] - 14889. 스타트와 링크

[URL]

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

14889번: 스타트와 링크

[풀이 과정]

* DFS 재귀 두번 해야한다.

 

 

1. 1~N까지의 수를 두개(A팀, B팀)로 나눠 모든 경우의 수 계산

2. 각각의 경우의 수에서 A팀 중 두개씩 묶어서 능력치 계산

 

ex)

N= 6, A팀 : [1, 2, 3]  B팀 : [4, 5, 6] 일 때

A팀 능력치: map[1][2] + map[2][1] + map[2][3] + map[3][2] + map[1][3] + map[3][1]

B팀 능력치: map[4][5] + map[5][4] + map[4][6] + map[6][4] + map[5][6] + map[6][5]

 

위에서 A팀 B팀 각각 N/2 개 원소 중 2개씩 묶어주는것도 DFS로 계산.

 

3. 모든 경우의 수 중 A팀 B팀 능력치 차이 중 최소를 구한다.

 

[소스 코드]

 

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int N;
int map[20][20];
bool check[21] = { 0, };
 
int aTeam[10];
int bTeam[10];
bool teamCheck[10] = { 0, };
 
int sumArr[2];
int sumA, sumB;
 
int cand[987654];
int candCnt = 0;
 
void init()
{
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
}
 
void calcA(int cnt)
{
    if (cnt == 2)
    {
        for (int i = 0; i < 2; i++)
        {
            sumA += map[sumArr[0] - 1][sumArr[1] - 1];
        }
 
        return;
    }
 
    for (int i = 0; i < N/2; i++)
    {
        if (teamCheck[i] == false)
        {
 
            teamCheck[i] = true;
            sumArr[cnt] = aTeam[i];
            cnt++;
 
            calcA(cnt);
 
            cnt--;
            teamCheck[i] = false;
        }
    }
}
 
void calcB(int cnt)
{
    if (cnt == 2)
    {
        for (int i = 0; i < 2; i++)
        {
            sumB += map[sumArr[0] - 1][sumArr[1] - 1];
        }
 
        return;
    }
 
    for (int i = 0; i < N / 2; i++)
    {
        if (teamCheck[i] == false)
        {
 
            teamCheck[i] = true;
            sumArr[cnt] = bTeam[i];
            cnt++;
 
            calcB(cnt);
 
            cnt--;
            teamCheck[i] = false;
        }
    }
}
 
int go()
{
    int res = 0;
 
    int bTeamCnt = 0;
 
    for (int i = 1; i <= N; i++)
    {
        int flag = 1;
        for (int j = 0; j < N/2; j++)
        {
            if (aTeam[j] == i)
                flag = flag * 0;
 
        }
        if (flag == 1)
        {
            bTeam[bTeamCnt++] = i;
        }
    }
 
    for (int i = 0; i < 10; i++)
    {
        teamCheck[i] = 0;
    }
    for (int i = 0; i < 2; i++)
    {
        teamCheck[i] = 0;
    }
    sumA = 0;
    calcA(0);
    sumA = sumA / 2;
 
    for (int i = 0; i < 10; i++)
    {
        teamCheck[i] = 0;
    }
    for (int i = 0; i < 2; i++)
    {
        teamCheck[i] = 0;
    }
 
    sumB = 0;
    calcB(0);
    sumB = sumB / 2;
 
    res = abs(sumA - sumB);
 
    return res;
}
 
 
 
void dfs(int cnt)
{
    if (cnt == N/2)
    {
        cand[candCnt++] = go();
        return;
    }
 
    for (int i = cnt+1; i <= N; i++)
    {
        if (check[i] == false && i >= aTeam[cnt-1])
        {
            check[i] = true;
            aTeam[cnt] = i;
            cnt++;
 
            dfs(cnt);
 
            cnt--;
            check[i] = false;
        }
    }
}
 
int main() {
 
    init();
 
    dfs(0);
 
    int Min = 987654;
    for (int i = 0; i < candCnt; i++)
    {
        if (cand[i] <= Min)
            Min = cand[i];
    }
 
    printf("%d\n", Min);
 
    return 0;
}