14889번 스타트와 링크

문제

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

해결 방법

N명이 있다. 우선 이 N명을 각각 A팀(N/2명), B팀(N/2명) 으로 나누어야 한다.

이 문제의 목적은 "두 팀 A와 B의 능력 차이를 최소가 되게 할 수 있는 팀으로 구성해야 된다" 이다.

따라서 모든 경우를 탐색해야 한다는 것을 알 수 있다. 그러므로 이 문제는 완전 탐색 문제가 된다.

그렇다면 완전 탐색 문제는 어떻게 하는 거지?

완전 탐색의 대표적인 알고리즘은 DFS와 BFS가 있다. (우선 문제를 풀려면 위 알고리즘에 대한 이해가 필요하다)

두 개의 팀이 이미 결정된 상태에서 각 팀의 능력치를 구하고 그 차이를 구해야하므로 'DFS'를 선택해야 한다는 것을 알 수 있다.

근데 DFS 알고리즘은 깊이 우선 탐색, 즉 탐색을 시작해서 목적지에 도착하면 바로 종료되는 알고리즘이다.

그렇기 때문에 여기서 백트래킹이라는 알고리즘을 접목시켜야 한다.

왜? 나는 지금 모든 경우를 탐색하고자 한다. 근데 탐색을 수행해서 목적지에 도착하면(두 개의 팀을 모두 결정했다면) 바로 종료하게 된다.

이것을 막기 위해 백트래킹을 써야한다는 것이다.

그렇다면 백트래킹을 어떻게 DFS에 접목해야 하는 것인가?

그 해답은 바로 왔던 길을 오지 않았다고 명시하면 된다.  

/*
14889번 스타트와 링크

삼성기출문제

완전탐색을 위해 dfs를 사용하였고 
dfs는 모든 경로를 돌다가 목적지를 찾으면 종료하기 때문에 백트레킹 방법을 사용하여 품


*/
 
#include<cstdio>
 
using namespace std;
int n,result=0,ans=99999999;
int arr[21][21];
bool visited[21];
 
 
void dfs(int v, int len);
void calculate();
int sum(int a[]);
int min(int a, int b) { return a > b ? b : a; }
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    dfs(0, 0);
    printf("%d", ans);
    return 0;
}
 
void dfs(int v, int len) { // 팀 선택 
    if (n / 2 == len)
        calculate();
    else {
        for (int i = v + 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i, len + 1);
            }
        }
    }
 
    // 백트래킹
    visited[v] = false;
}
 
void calculate() { // 팀을 결정했고 
    int a[11];
    int b[11];
    int ai = 1, bi = 1;
 
    for (int i = 1; i <= n; i++) {
        if (visited[i]) 
            a[ai++] = i;
        else 
            b[bi++] = i;
    }
 
    int asum = sum(a);
    int bsum = sum(b);
 
    if (asum > bsum)
        result = asum - bsum;
    else
        result = bsum - asum;
 
    ans = min(ans, result);
}
 
int sum(int a[]) { // 계산한다.
    int result = 0;
    int len = n / 2;
 
    for (int i = 1; i <= len; i++) {
        for (int j = i + 1; j <= len; j++) {
            result += arr[a[i]][a[j]];
            result += arr[a[j]][a[i]];
        }
    }
 
    return result;
}