[BOJ] 백준 [14889] 스타트와 링크 JAVA

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

14889번: 스타트와 링크

[문제]

[풀이]

만약 , 1번과 2번이 같은 팀이 된다면 능력치의 합은 S12+S21 = 5이다.
만약 , 1, 2, 3번이 같은 팀이 된다면 능력치의 합은 S12+S21+S23+S32+S13+S31 이다.

즉 , 완전탐색으로 모든 조합을 맞춰보면서 , 진행한 깊이(depth)가 한 팀(n/2) 만큼 진행했을 때,
visit=true 인 팀의 시너지 총합을 A팀 이라 하고 , 이때 
visit=false 인 팀의 시너지 총합은 B팀이 된다.

A-B의 차이 최소값을 탐색을 완료할 때 까지 갱신 시켜주면서 리턴하면 끝

import java.util.*;
import java.io.*;
import java.util.stream.*;
 
 
public class Main {
 
    static boolean[] visit;
    static int[][] info;
    static int n,min=Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        info = new int[n][n];
        visit = new boolean[n];
        for(int i=0;i<n;i++)
            info[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
 
        dfs(0,0);
        System.out.println(min);
 
    }
    static void dfs(int cur,int depth){
 
        if(depth==n/2){
            //todo
            getMinDiff();
        }
 
        for(int next=cur;next<n;next++){
            if(!visit[next]){
                visit[next]=true;
                dfs(next,depth+1);
                visit[next]=false;
            }
        }
    }
 
    static void getMinDiff(){
 
        int teamA=0,teamB=0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(visit[i]&&visit[j]){
                    teamA+=info[i][j];
                    teamA+=info[j][i];
                }else if(!visit[i]&&!visit[j]){
                    teamB+=info[i][j];
                    teamB+=info[j][i];
                }
            }
        }
 
        int result = Math.abs(teamA - teamB);
        min = Math.min(result,min);
    }
}