백준 14889 스타트와 링크(Java)

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

14889번: 스타트와 링크

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {

  static int n;
  static int[][] arr = new int[21][21];
  static boolean visit[] = new boolean[21];
  static int min = Integer.MAX_VALUE;

  public static void dfs(int s, int num) {
    
    if(num == n / 2) {
      int a = 0;
      int b = 0;
      
      for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
          if(visit[i] == true && visit[j] == true) a += arr[i][j];
          if(visit[i] == false && visit[j] == false) b += arr[i][j];
        }
      }

      min = Math.min(Math.abs(a - b), min);
      return;
    }

    for(int i = s; i <= n; i++) {
      if(visit[i] == false) {
        visit[i] = true;
        dfs(s + 1, num + 1);
        visit[i] = false;
      }
    }
    
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

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

    dfs(1, 0);
    
    System.out.println(min);
  }

}