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

● 문제

 

 

● 풀이

package backJoon.step15.백트래킹.스타트와링크;

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 MIN = Integer.MAX_VALUE;

    /**
     * 스타트팀과 링크팀으로 나눈 시너지 효과의 최솟값
     * 
     * @param args
     * @throws NumberFormatException
     * @throws IOException           :
     *
     * @since 2022. 8. 19. 오후 1:59:56
     * @author "KyungHun Park"
     * 
     * @modified 2022. 8. 19. 오후 1:59:56 || Kyunghun Park || 최초 생성
     *
     */
    public static void main(String[] args) throws NumberFormatException, 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(MIN);
    }

    /**
     * dfs를 통해 최대 방문 시 최솟값을 확인하기 위한 함수
     * 
     * @param value : 현재 방문 위치
     * @param depth : 현재 깊이
     *
     * @since 2022. 8. 19. 오후 2:00:46
     * @author "KyungHun Park"
     * 
     * @modified 2022. 8. 19. 오후 2:00:46 || Kyunghun Park || 최초 생성
     *
     */
    private static void dfs(int value, int depth) {
        if (depth == N / 2) {
            point();
            return;
        }

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

    /**
     * 가장 깊은 곳 까지 방문 시 두 팀의 능력치가 최솟값인지 확인
     * 
     *
     * @since 2022. 8. 19. 오후 2:02:06
     * @author "KyungHun Park"
     * 
     * @modified 2022. 8. 19. 오후 2:02:06 || Kyunghun Park || 최초 생성
     *
     */
    private static void point() {
        // 스타크팀 능력치 합
        int teamStart = 0;
        // 링크팀 능력치 합
        int teamLink = 0;

        // 점수의 합
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {

                if (visited[i] && visited[j]) {
                    teamStart += arr[i][j];
                    teamStart += arr[j][i];
                } else if (!visited[i] && !visited[j]) {
                    teamLink += arr[i][j];
                    teamLink += arr[j][i];
                }
            }
        }

        // 스타크팀과 링크팀의 점수차를 절대값
        int resPoint = Math.abs(teamStart - teamLink);

        // 0인 경우보다 작은 경우는 없으니 0을 출력하고 바로 종료
        if (resPoint == 0) {
            System.out.println(0);
            System.exit(0);
        }

        // 최솟값 갱신
        MIN = Math.min(resPoint, MIN);
    }

}