백준 14889번 : 스타트와 링크

• 분류: 백트래킹

코드

#include <iostream>
#include <vector>
using namespace std;

int n;
int point[20][20];
bool visit[20];
int min_val = INT32_MAX;

void backtrack(int depth, int back) {
    if(depth==n/2) {
        vector<int> team;
        vector<int> other;
        for(int i=0 ; i<n ; i++) {
            if(visit[i]) team.push_back(i);
            else other.push_back(i);
        }
        int team_score=0;
        int other_score=0;
        for(int t1 : team) {
            for(int t2 : team) {
                if(t1==t2) continue;
                team_score += point[t1][t2];
            }
        }
        for(int o1 : other) {
            for(int o2 : other) {
                if(o1==o2) continue;
                other_score += point[o1][o2];
            }
        }
        if(min_val>abs(team_score-other_score)) min_val = abs(team_score-other_score);
        return;
    }

    for(int i=back+1 ; i<n ; i++) {
        if(!visit[i]) {
            visit[i]=true;
            backtrack(depth+1, i);
            visit[i]=false;
        }
    }
}

int main() {
   std::cin >> n;

   for(int i=0 ; i<n ; i++) {
       for(int j=0 ; j<n ; j++) {
           cin >> point[i][j];
       }
       visit[i]=false;
   }

   visit[0]=true;
   backtrack(1, -1);
   cout << min_val;
}

• 코멘트
  
  문제를 푸는 것 자체는 간단하다. nxn 행렬을 입력받아 저장하고, 재귀함수를 이용해 depth=n/2까지 탐색한 후 뽑힌 두 팀의 시너지 점수를 빼면 된다.
  하지만 문제의 함정은 시간이다. naive하게 nx(n-1)x(n-2)x...x(n/2+1) 개의 경우의 수를 모두 시도하면 시간 초과가 뜨게 된다.
  따라서 이 문제는 순열이 아닌 조합으로 풀어야 한다. 이를 위해서 back이라는 변수 하나를 더 두었는데, 이는 다음 팀원을 이전 팀원 다음 인덱스부터 찾기 위함이다.
  총 10명일 때 1 2 3 4 , 1 2 3 5, …. 1 2 6 8, 1 2 6 9 까지 왔으면 그 다음 조합은 1 2 7 8이지, 1 2 7 3 이 아닌 원리이다.