[백준] 14889. 스타트와 링크

문제 

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





풀이

문제가 조금 복잡할 수도 있고, 주의할 점도 있다. 예시로 {1, 2, 3, 4, 5, 6} 이라는 멤버에서 {1, 2, 3} 과 {4, 5, 6} 팀을 뽑았다고 생각해보자.

• n개의 팀에서 n / 2씩 분리하는 것을 생각 해줘야 한다. 이것은 [14888. 연산자 끼워넣기] 에서 사용했던 방법처럼 DFS로 경우의 수를 모두 구해줄 수 있다. 주의할 점은, {1, 2, 3} {4, 5, 6} 과 {2, 1, 3} {5, 4, 6}은 같은 그룹이라는 것이다. 따라서 이런 중복되는 그룹을 배제하고 묶는 경우를 구해줘야 한다. 이 점을 주의하자. (안 하면 시간초과가 날 것이다.)
• 분리된 팀의 능력치는 첫번째 팀은 S12 + S21 + S13 + S31 + S23 + S32이 나올테고, 두번째 팀은 S45 + S54 + S46 + S64 + S56 + S65 가 나올 것이다. (물론 S11, S22, S33, S44, S55, S66 같은 경우는 0이므로 더해줘도 상관은 없다.) 따라서 team1, team2의 멤버들을 2개의 벡터로 나눠준 후, 각각 벡터의 index가 0일 때, 0 ~ vector.size까지의 값을 다 더해주고, index가 2일 때, index가 3일 때, ... 를 전부 구해준다. 능력치는 p[21][21]안에 있으므로 p[v[i]][v[j]]와 같은 식이 될 것이다.
• 능력치의 차가 최소가 된다고 했는데, 이 때 음수값은 나오지 않으므로 team1 과 team2 중에서 큰 값에서 작은 값을 빼줘야한다. 또는 abs를 이용해서 절대값을 취해줘도 무방하다. abs는 <stdlib.h> 안에 정의 되어 있다.

계산이 어떤 식으로 나오는지 궁금하면 주석에 달린 출력을 주석 해제하고 확인해보자.

//
//  14889.cpp
//  BJ
//
//  Created by 신기열 on 24/10/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int n;
int visited[21];
int p[21][21];
int answer = 100000000;

// 각 팀의 능력치를 구하기 위한 함수
void calc(vector<int> v){
    // team1이 v 안에 있고 v 안에 없는 멤버들은 nv 안에 넣는다
    vector<int> nv;
    int team1 = 0, team2 = 0;
    // team1을 제외한 나머지 멤버를 team2에 넣는다.
    for(int i = 1; i <= n; i++){
        bool isExist = false;
        for(int j = 0; j < v.size(); j++){
            if(v[j] == i){
                isExist = true;
                break;
            }
        }
        if(!isExist) nv.push_back(i);
    }
    
//    cout << "{ ";
//    for(int i = 0; i < v.size(); i++){
//        cout << v[i] << " ";
//    }
//    cout << "}";
//
//    cout << "      { ";
//    for(int i = 0; i < v.size(); i++){
//        cout << nv[i] << " ";
//    }
//    cout << "}    answer : ";

    // team1의 능력치를 구한다. team1의 첫번째 멤버 당(v[i]) 두번째 멤버, 세번째 멤버, 네번째 멤버... 의 능력치를 차례로 더해주고,
    // 두번째, 세번째, 네번째, ... 에도 똑같이 계산해준다.
    for(int i = 0; i < v.size(); i++){
        for(int j = 0; j < v.size(); j++){
            team1 = team1 + p[v[i]][v[j]];
        }
    }
    // team2의 능력치를 구한다.
    for(int i = 0; i < nv.size(); i++){
        for(int j = 0; j < nv.size(); j++){
            team2 = team2 + p[nv[i]][nv[j]];
        }
    }
//    cout << "max(" << max(team1, team2) << ") - min(" << min(team1, team2) << ") = " << max(team1, team2) - min(team1, team2) << '\n';
    // max(team1, team2) - min(team1, team2) = |team1 - team2| 의 최솟값을 구해준다.
    answer = min(answer, max(team1, team2) - min(team1, team2));
    
}

void DFS(vector<int> v, int tmp[21]){
    
    int tvisited[21];
    // 한 팀에 들어갈 수 있는 멤버의 수는 n / 2이므로 멤버 벡터에 n / 2개의 원소가 들어가있으면 계산하고 끝낸다.
    if(v.size() == n / 2){
        calc(v);
        return;
    }
    // tv, tvisited 초기화
    vector<int> tv(v.size());
    for(int i = 0; i < v.size(); i++){
        tv[i] = v[i];
    }
    
    for(int i = 1; i <= n; i++){
        tvisited[i] = tmp[i];
    }
    // 특정 멤버에 대해 탐색을 한 적이 없으면, 즉 어떤 팀에 포함되어 있지 않으면 team1에 넣어주고 DFS를 돌려준다. DFS가 끝나면 다시 team1에서
    // 빼준다. 이 때 visited를 초기화하지 않는 이유는 만약 1번 멤버 탐색이 끝났으면 1번 멤버에 대한 모든 케이스 탐색이 끝난 것이므로 다시
    // 1번 멤버를 포함해서 케이스를 구해줄 필요가 없다.
    for(int i = 1; i <= n; i++){
        if(tvisited[i] == 0){
            tvisited[i] = 1;
            tv.push_back(i);
            DFS(tv, tvisited);
            tv.pop_back();
        }
    }
}


int main(){
    
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> p[i][j];
        }
    }
    
    vector<int> v;
    DFS(v, visited);
    cout << answer;
    
    return 0;
}