[백준] 스타트와 링크 - 자바

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

14889번: 스타트와 링크

문제 풀이

팀이 총 2개로 나눠지기 때문에 dfs를 통해 가능한 팀의 조합을 구한다. 이때 그래프 탐색에서 사용하는 boolean타입의 visit을 생각하면 편하다. 즉 visit에 true가 총 플레이어 수의 절반이 됐다면 팀 2개가 구성이 됐다는 뜻이다.

팀이 구성되면 점수차이를 계산하여 최솟값을 업데이트 한다.

 

코드

package 백준;

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

public class b14889 {
    static boolean[] visit;
    static int n;
    static int[][] mat;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        // init
        visit = new boolean[n];
        mat = new int[n][n];
        for (int i = 0; i < n; i++) {
            mat[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
        }

        dfs(0, 0);

        System.out.println(answer);
    }

    static void dfs(int cnt, int index) {
        if (cnt == n / 2) {
            int diff = 0;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (visit[i] && visit[j]) {
                        diff += mat[i][j];
                    } else if (!visit[i] && !visit[j]) {
                        diff -= mat[i][j];
                    }
                }
            }

            answer = Math.min(answer, Math.abs(diff));
        }
        else {
            for (int i = index; i < n; i++) {
                if (!visit[i]) {
                    visit[i] = true;
                    dfs(cnt + 1, i + 1);
                    visit[i] = false;
                }
            }
        }
    }
}