스타트와 링크 - Java, 백트래킹

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

package Samsung;


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

public class Startandlink {
    static int n;
    static int total =0;
    static int min = 99999999;
    static boolean [] check = new boolean [20];
    static void backTracking(int count,int[][]arr,int idx){

        if(count == n/2){
            int starttotal=0;
            int linktotal =0;
            for(int i=0; i<n; i++){
                for(int j=i+1; j<n; j++){
                    if(check[i]==true && check[j]==true) { //둘다 start의 일부라면
                        starttotal += arr[i][j];
                        starttotal += arr[j][i];  
                    }
                    else if(check[i]==false && check[j]==false) { //둘다 link의 일부라면
                        linktotal += arr[i][j];
                        linktotal += arr[j][i];
                    }
                }
            }

            if(Math.abs(linktotal-starttotal)<min){
                min = Math.abs(linktotal-starttotal);

            }
            return;
        }

        for(int i=idx; i<n; i++){  //idx부터 시작해야지 시간 초과 안남!

            if(check[i]==false){
                check[i]=true;
                backTracking(count+1,arr,i+1);
                check[i]=false;
            }

        }
        return;

    }



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

        n = Integer.parseInt(br.readLine());
        int [][]arr = new int[n][n];

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

        backTracking(0,arr,0); //backtracking 을 통해 모든 경우를 생각해 준다. 
        System.out.println(min);

    }
}