[백준 14889] 스타트와 링크

 

백트래킹으로 가능한 모든 팀을 구성한 뒤 최솟값을 구했다.

 

위의 예제로 설명하겠다.

 

1. 인덱스별로 DFS를 한다.

2. n/2 일때 방문한 노드2개 방문안한 노드2개 이므로 방문한 쪽/ 안한 쪽으로 팀을 나눈다.

3. 배열이나 리스트에 각 노드를 담아서 능력치 차이를 계산한다.

 

백트래킹을 제외하면 자기 스타일대로 구현을 하면 된다.

 

public class Main {
    
    static int n;
    static int a[][];
    static boolean visited[];
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        a = new int[n][n];
        visited = new boolean[n];
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++)
                a[i][j] = Integer.parseInt(st.nextToken());
        }
        
        dfs(0, 0);
        
        System.out.println(min);
    }
    
    public static void dfs(int idx, int len) {
        if(len == n/2) {
            int startTeam[] = new int[n/2 + 1];
            int linkTeam[] = new int[n/2 + 1];
            int s = 0;
            int l = 0;
            for(int i=0; i<n; i++) {
                if(visited[i])
                    startTeam[s++] = i;
                else
                    linkTeam[l++] = i;
            }
            
            int start = 0;
            int link = 0;
            for(int i=0; i<n/2; i++) {
                for(int j=i+1; j<n/2; j++) {
                    start += a[startTeam[i]][startTeam[j]] + a[startTeam[j]][startTeam[i]];
                    link += a[linkTeam[i]][linkTeam[j]] + a[linkTeam[j]][linkTeam[i]];
                }
            }
            
            min = Math.min(min, Math.abs(start - link));
            return;
        }
        
        for(int i=idx; i<n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                dfs(i, len+1);
                visited[i] = false;
            }
        }
    }
}