[Silver 1] 14889 스타트와 링크

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

 

백트레킹을 사용하는 문제이다.

idx와 cnt라는 매개변수를 통해 백트레킹을 구현하였다.

idx를 통해 다음 팀원을 구하는 과정에서 이전에 선택한 팀원을 고를지 선택하는 과정이 생기지 않도록 하였다. (반복횟수를 적게함)

cnt 변수를 통해 depth를 조절하였다.

팀원을 선택할 때는 N/2명을 선택하면 모든 팀에 팀원을 배치하였다고 볼 수 있다.

start팀이 N/2명을 골랐다면 link팀은 start팀이 고른 이외의 사람이 들어가기 때문이다.

 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int N;
int S[21][21];
bool visited[21];
int answer = 987654321;

// 0 1 2 3

// 0 1
// 2 3

// 0 2
// 1 3
void dfs(int idx, int cnt){
    if(cnt == N/2){
        int start = 0, link = 0;
        for(int i = 0;i<N;i++){
            for(int j = 0;j<N;j++){
                if(visited[i] && visited[j]){
                    start += S[i][j];
                }
                else if(!visited[i] && !visited[j]){
                    link += S[i][j];
                }
            }
        }
        answer = min(answer,abs(start - link));
        return;
    }
    for(int i = idx;i<N;i++){
        if(!visited[i]){
            visited[i] = true;
            dfs(i + 1,cnt + 1);
            visited[i] = false;
        }
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N;
    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++)
            cin>>S[i][j];
    }

    dfs(0, 0);
    cout<<answer;
}