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

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

14889번: 스타트와 링크

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    public static int[][] arr;
    public static boolean[] visited;
    public static int n;

    public static int min = Integer.MAX_VALUE;

    public static void dfs(int cnt, int s){ // 조합
        if(cnt==n/2){

            int start = 0;
            int link = 0;

            for(int i=1; i<n; i++){
                for(int j=i+1; j<=n; j++){
                    if(visited[i] && visited[j]){ // 두 사람이 true면 스타트팀
                        start += arr[i][j] + arr[j][i];
                    }
                    else if(!visited[i] && !visited[j]){ // 두 사람이 false면 링크팀
                        link += arr[i][j] + arr[j][i];
                    }
                }
            }
            int gap = Math.abs(start-link); // 두 팀의 점수 차이

            min = Math.min(min, gap);
            return;
        }

        for(int i=s; i<=n; i++){ // 중복된 수열이 나오지 않도록 오름차순으로 하기 위해 s부터 시작
            if(visited[i]) continue;

            visited[i] = true;
            dfs(cnt+1, i+1); // 카운트 증가, i증가(오름차순 위해)
            visited[i] = false;

        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        arr = new int[n+1][n+1];
        visited = new boolean[n+1];

        StringTokenizer st;

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0, 1);

        System.out.println(min);
    }
}