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

❓문제

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

📌유형

백트래킹

✍🏻풀이

고르지 않은 선수라면 true로 바꾸고 선택한 선수 + 1 부터 추적.
n/2명을 고르고 스타트팀 점수와 링크 팀 점수를 계산.
두 계산의 차의 절댓값과 최솟값을 비교하여 가장 차가 작은 최솟값 찾기.

💻코드

import java.util.*;
import java.io.*;

public class Main {

    static int n;
    static int min = Integer.MAX_VALUE;
    static int[][] s;
    static boolean[] visited;

    static void backtracking(int len, int idx) {
        if (len == n / 2) {
            int start = 0;
            int link = 0;

            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (visited[i] && visited[j]) {
                        start += s[i][j] + s[j][i];
                    } else if (!visited[i] && !visited[j]) {
                        link += s[i][j] + s[j][i];
                    }
                }
            }

            min = Math.min(min, Math.abs(start - link));
            return;
        }

        for (int i = idx; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                backtracking(len + 1, i + 1); /** 현재 인덱스 위치 + 1 **/
                visited[i] = false;
            }
        }
    }

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

        n = Integer.parseInt(r.readLine());
        s = new int[n][n];
        visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(r.readLine(), " ");
            for (int j = 0; j < n; j++) {
                s[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        backtracking(0, 0);
        System.out.println(min);
    }
}

💡새로 배운 내용

절댓값 함수는 Math 라이브러리