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

#include <iostream>
#include <algorithm> // min
#include <vector>
#include <cmath> // abs(절댓값)
using namespace std;

int map[21][21]; // 세로 i, 가로 j

bool visited[21]; // 방문 여부
int N;
int Min = 999999999;

void DFS(int num, int cnt){
  if(cnt == N / 2){
    // 팀 저장 - 지역변수로 해야 별도의 초기화 불필요, 모든 수열에 따라 다른 팀 저장
    vector<int> team1;
    vector<int> team2;

    // 팀 별 능력치 저장
    int tmp1 = 0;
    int tmp2 = 0;

    for(int i = 1; i <= N; i++){ // 팀 저장
      if(visited[i]){ // 골라진 수열의 수
        team1.push_back(i); // team1에 저장
      } else {
        team2.push_back(i); // team2에 저장
      }
    }

    for(int i = 0; i < N/2; i++){
      // printf("team1 : %d team2 : %d\n", team1[i], team2[i]);
      for(int j = i; j < N/2; j++){
        tmp1 += map[team1[i]][team1[j]] + map[team1[j]][team1[i]];
        tmp2 += map[team2[i]][team2[j]] + map[team2[j]][team2[i]];
      }
    }

    int tmp = abs(tmp1 - tmp2);
    // printf("tmp : %d tmp1 : %d tmp2 : %d\n", tmp, tmp1, tmp2);
    
    Min = min(Min, tmp);
    return;
  }

  for(int i = num; i <= N; i++){
    visited[i] = true; // visited면 순열 골라진 것
    DFS(i+1, cnt + 1);
    visited[i] = false;
  }
}

int main(int argc, char** argv){
  scanf("%d", &N);

  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++){
      scanf("%d", &map[i][j]); // 능력치 표 입력받기
    }
  }

  visited[1] = true;
  DFS(2, 1); // 2번부터 체크, 1은 이미 팀 1에 속해있다고 가정

  printf("%d", Min);

  return 0;
}

• 팀을 짜기 위해서는 팀에 속할 2/N명의 사람을 고르면 된다. 따라서 순열과 같다. 1~N까지의 수 중에서 2/N개를 구하는 것과 같다. 순열을 구할때는 백트래킹을 이용해서 구한다. 팀의 순서는 중요하지 않으므로 1번은 이미 팀에 속해있다고 보고 다음 값부터 구해주었다.

• 골라진 순열의 값은 visited에 true로 체크되어 있는 것이 골라진 수이다. 따라서 반복문을 돌면서 각각의 팀을 저장해준다. 동적 할당 배열이 필요하기 때문에 vector를 사용하여 팀을 저장하였다.

• 팀이 (1, 2, 4) (3, 5, 6) 이렇게 나누어졌다고 했을 때 (1, 2, 4)의 능력치를 구하려면 (1, 2), (1, 4), (2, 4) 이렇게 세 가지를 구해주어야한다. 때문에 2중 for문을 이용해 모든 경우를 탐색해주어야한다.

• 절댓값을 구할때는 STL 라이브러리 cmath의 abs를 사용한다.