[백준] 14889번 : 스타트와 링크 (JAVA)

인간몽쉘김통통·2023년 11월 24일

DFS 백준 브루트포스 알고리즘

백준

목록 보기

25/92

문제

이해

짝수 명의 사람들을 두 팀으로 나누려고 한다. 최대한 비슷한 전력으로 팀을 나누기 위해 아래와 같은 표를 사용한다.

팀의 전력은 개인의 능력의 합이 아닌 서로가 팀이 됐을 때의 능력치의 합으로 계산한다.

위의 표에서 i와 j는 각 선수를 의미하고 같은 팀이 됐을 때의 능력치를 의미한다

예를 들어, 1번과 2번이 같은 팀이 되는 경우 팀의 전체 능력치는 S(1,2) + S(2,1)이 된다.

예시는 전체 인원이 4명이기 때문에 2명씩 팀이 되지만 그 이상인 경우는 어떻게 계산할까?

가능한 순서쌍 조합을 모두 합하면 된다. 예를 들어, 6명을 3명으로 나누는 경우 (1, 3, 5), (2, 4, 6)으로 팀을 나눈다고 하자.

그렇다면 1팀의 능력치는 S(1, 3) + S(3, 1) + S(1, 5) + S(5, 1) + S(3, 5) + S(5, 3) 이 된다. 2팀도 마찬가지로 계산하면 된다.

위와 같은 방식으로 팀의 능력치의 차이가 최소일때의 값을 구하면 된다.

접근

크게 두 과정으로 진행된다.

팀 구성하기
능력치 비교하기

1번의 과정은 가능한 순서쌍을 뽑아야 한다. 기본적으로 주어진 자료만으로 그리디를 적용할 수는 없을 것 같다. 따라서, 완전탐색이 필요해 보인다.

뽑는 방식은 뽑힌 전력이 있는 선수를 visited 배열 정보에 저장하여 뽑게 한다. 노드의 방문 여부를 확인하는 것과 같다.

dfs를 사용해서 오름차순으로 팀을 구성하는 경우를 모두 탐색할 수 있다.

뽑을 때 주의해야 하는 것은 팀의 구성에는 순서가 없는 것이다. 가령, 3명의 팀을 뽑을 때
(1, 3, 5)와 (3, 1, 5)는 같다.

따라서, 이러한 중복을 피할 수 있는 코드를 작성해야 한다.

그렇다면 2번 능력치는 어떻게 비교하면 될까? 어렵지 않다.

1번에서 뽑은 팀의 정보는 visited 배열에 있을 것이다. 한 분기가 끝에 도달했을 때 visited 내의 true값인 인덱스는 1팀, false값인 인덱스는 2팀이 된다.

이를 바탕으로 팀의 능력치 합을 구하면 된다. 능력치를 구할 때는 2차원 배열을 통해서 팀 구성원의 인덱스를 조합하여 합산하면 된다.

코드

package java_baekjoon;

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

public class prob14889 {
    static int N;
    static int[][] info;
    static boolean[] visited;
    static int ans = Integer.MAX_VALUE;

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

        N = Integer.parseInt(br.readLine());

        visited = new boolean[N];
        info = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                info[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0, -1);

        System.out.println(ans);
    }

    static void dfs(int depth, int prev_select) {
        if (depth == N / 2) {
            ArrayList<Integer> selected_1 = new ArrayList<>();
            ArrayList<Integer> selected_2 = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                if (visited[i]) {
                    selected_1.add(i);
                } else {
                    selected_2.add(i);
                }
            }

            int ability_1 = Cal_Ability(selected_1);
            int ability_2 = Cal_Ability(selected_2);

            int dif = Math.abs(ability_1 - ability_2);
            if (ans > dif) {
                ans = dif;
            }

            return;
        }

        for (int i = prev_select + 1; i < N; i++) {
            if (visited[i]) {
                continue;
            }

            visited[i] = true;
            dfs(depth + 1, i);
            visited[i] = false;
        }
    }

    static int Cal_Ability(ArrayList<Integer> team) {
        int sum = 0;

        for (int i = 0; i < team.size(); i++) {
            for (int j = i + 1; j < team.size(); j++) {
                sum += (info[team.get(i)][team.get(j)] + info[team.get(j)][team.get(i)]);
            }
        }
        return sum;
    }
}