[백준 14889번] 스타트와 링크 :: 늦깎이 IT

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

1. N명을 반으로 나눠 한 팀은 스타트 팀, 나머지 한 팀은 링크 팀으로 나눈다.

2. 팀을 나눌 때에는 DFS를 활용해서 모든 경우의 수를 구한다.

2. 팀을 나눴다면, 조건에 의한 팀의 능력치를 계산한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int N, ans = Integer.MAX_VALUE;
    public static int[][] map;
    public static boolean[] team;
    public static int[] dirX = new int[] { 0, 0, -1, 1 };
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        map = new int[N][N];
        team = new boolean[N + 1];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0, 0);
        System.out.println(ans);
    }
 
    public static void dfs(int depth, int numOfPerson) {
 
        if (depth > N)
            return;
 
        if (numOfPerson == N / 2) {
 
            List<Integer> start = new ArrayList<>();
            List<Integer> link = new ArrayList<>();
 
            for (int i = 0; i < N; i++) {
                if (team[i]) {
                    start.add(i);
                } else {
                    link.add(i);
                }
            }
 
            int startTeam = 0;
            int linkTeam = 0;
            
            for (int i = 0; i < start.size() - 1; i++) {
                
                for (int j = i + 1; j < start.size(); j++) {
                    
                    startTeam += map[start.get(i)][start.get(j)];
                    startTeam += map[start.get(j)][start.get(i)];
                    
                    linkTeam += map[link.get(i)][link.get(j)];
                    linkTeam += map[link.get(j)][link.get(i)];
                }
            }
 
            ans = Math.min(ans, Math.abs(startTeam - linkTeam));
            return;
        }
 
        team[depth] = true;
        dfs(depth + 1, numOfPerson + 1);
 
        team[depth] = false;
        dfs(depth + 1, numOfPerson);
 
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
 
}
 
class Node {
    int row;
    int col;
 
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
 
}