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

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

15661번: 링크와 스타트

 

각 팀원이 꼭 같지 않으모르 1명이상부터 모두 탐색하는 로직을 넣어야 함

 

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());
        }
    }
    // 팀별로 인원이 같지 않아도 됨, 1명이상이면 팀
    for(int i = 1; i <= N; i++) {
    	dfs(i, 0, 0);
    }    

    	System.out.println(min);
    }


    public static void dfs(int team, int start, int depth) {
        if(team == depth) {
        	min = Math.min(min, diff());
        	return;
        }  

        for(int i = start; i < N; i++) {
            if(!visit[i]) {
                visit[i] = true;
                dfs(team, 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);
    }

}