[백준 | Java] 15661 링크와 스타트

내 풀이

14889번 스타트와 링크 문제와 비슷한듯 다른 문제였다.
👉 14889번 스타트와 링크 풀이

이 문제 또한 모든 경우의 수를 검사하는 브루트포스의 DFS로 풀었다.

1. num번째 사람을 스타트 팀에 넣어(visited[num] = true) num+1을 인수로 넣어 재귀를 진행하고,
   num번째 사람을 링크 팀에 넣어(visited[num] = false) num+1을 인수로 넣어 재귀를 진행한다.
2. num이 N일 때 종료조건 진행한다.
3. 종료조건 내에서 두 팀원이 서로 같은 팀일 때 능력치를 계산해 반환한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] arr;
    static boolean[] visited;
    static int minCal = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        visited = new boolean[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);
        System.out.println(minCal);
    }

    static void dfs(int num) {
        if (num == N) {
            int start = 0;
            int link = 0;
            int cal;

            for (int i = 0; i < N; i++) {
                for (int j = i+1; j < N; j++) {
                    // 두 팀원이 서로 다른 팀일 때 continue
                    if (visited[i] != visited[j])
                        continue;
                    // 두 팀원이 서로 같은 팀일 때 능력치 계산
                    if (visited[i])
                        start += arr[i][j] + arr[j][i];
                    else
                        link += arr[i][j] + arr[j][i];
                }
            }
            cal = Math.abs(start - link);
            minCal = Math.min(cal, minCal);
            return;
        }

        // num번째 사람 선택해 스타트 팀에 넣기
        visited[num] = true;
        dfs(num + 1);

        // num번째 사람 선택해 링크 팀에 넣기
        visited[num] = false;
        dfs(num + 1);
    }
}