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

내 풀이

문제에서 Sij는 Sji와 다를 수도 있다고 했으므로 규칙이 없이 진행된다.
따라서 작은 문제로 큰 문제를 해결할 수 있는 DP로는 풀 수 없게 된다.

그럼 모든 경우의 수를 검사하는 브루트포스의 DFS로 풀어본 풀이는 다음과 같다.

1. N은 무조건 짝수이고, 언제나 두 팀으로만 나누면 되기 때문에 한 번 탐색할 때 N/2번만(종료조건) 백트래킹
2. 방문 표시가 된 요소들은 임의로 start팀으로, 방문 표시가 되지 않은 요소들은 link팀으로 간주하여 능력치를 계산
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, 0);
        System.out.println(minCal);
    }

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

            for (int j = 0; j < N-1; j++) {
                for (int k = j+1; k < N; k++) {
                    if (visited[j] && visited[k]) {
                        start += arr[j][k];
                        start += arr[k][j];
                    } else if (!visited[j] && !visited[k]) {
                        link += arr[j][k];
                        link += arr[k][j];
                    }
                }
            }
            cal = Math.abs(start - link);
            minCal = Math.min(cal, minCal);
            return;
        }

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