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

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

14889번: 스타트와 링크

 

 

import java.util.*;
import java.io.*;

public class Main {

    public static int N;
    public static boolean[] visit;
    public static int[][] arr;
    public static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        visit = new boolean[N];
        arr = new int[N][N];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0, 0);
        System.out.println(min);
    }


    public static void dfs(int start, int depth) {
        // 팀을 나누기 위해 depth는 N / 2 까지
        if(N/2 == depth) {
        	min = Math.min(min, diff());
        	return;
    	}  

		// 중복방지를 위해 start를 올려줌
        for(int i = start; i < N; i++) {
            if(!visit[i]) {
                visit[i] = true;
                dfs(i + 1, depth+1);
                visit[i] = false;
            }
        }
    }

    // 스타트와 링크의 차이를 구한다.
    public static int diff() {
        int start = 0; // visit = true
        int link = 0; // visit = false
        for(int i = 0; i < N - 1; i++) {
            for(int j = i + 1; j < N ; j++) {

                if(visit[i] && visit[j]) {
                	start += arr[i][j] + arr[j][i];
                } else if(!visit[i] && !visit[j]) {
                	link += arr[i][j] + arr[j][i];
                }
            }
        }

        return Math.abs(start-link);
    }

}