백준 14889 - 스마트와 링크

백트래킹을 활용한 문제입니다.

조합의 개념이 들어가서 상당히 애먹었기때문에 다른 분의 풀이를 참조했습니다.

package com.company;

import java.util.LinkedHashMap;
import java.util.Scanner;

public class boj14889 {
    static int N;
    static int[][] map;
    static boolean visited[];
    static int min=99999999;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N+1][N+1];
        visited = new boolean[N+1];

        for(int i=1; i<N+1; i++){
            for(int j=1; j<N+1; j++){
                map[i][j] = sc.nextInt();
            }
        }

        dfs(1,0);

        System.out.println(min);



    }

    static void dfs(int start, int count){
        if(count == N/2){
            min = Math.min(min, getDifference());
            return;
        }

        for(int i=start; i<N+1; i++){
            if(visited[i] != true){
                visited[i] = true;
                dfs(i+1, count+1);
                visited[i] = false;
            }
        }
    }

    static int getDifference(){
        int sumSmart = 0;
        int sumLink = 0;

        for(int i=1; i<N+1; i++){
            for(int j=1; j<N+1; j++){
                if(visited[i] == true && visited[j] == true){
                    sumSmart += map[i][j];
                }

                if(visited[i] == false && visited[j] == false){
                    sumLink += map[i][j];
                }
            }
        }

        return Math.abs(sumSmart-sumLink);
    }

    static void printMap(){
        for(int i=1; i<N+1; i++){
            for(int j=1; j<N+1; j++){
                System.out.print(" " + map[i][j]);
            }
            System.out.println();
        }
    }

    static void printVisited(){
        for(int i=1; i<N+1; i++){
            System.out.println(" " + visited[i]);
        }
    }
}