[Baekjoon Online Judge] 14889번: 스타트와 링크

14889번: 스타트와 링크

요구사항

 - 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

 - BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

입력

 - 첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

 - 첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

---

백트래킹으로 만들 수 있는 팀 조합을 확인하고 최솟값을 구하는 문제이다.

 

private static void combination(int start, int depth) {
    if (depth == n / 2) {
        min = Math.min(min, getDifference());
        return;
    }

    for (int i = start; i <= n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            combination(i + 1, depth + 1);
            visited[i] = false;
        }
    }
}

 

총 인원이 n인 경우 스타트 팀과 링크 팀으로 팀을 나누기 위해서는 주어진 인원에 반이 될 때 까지 인원을 추가한다. 각 인원을 반반씩 나눴는데 이것을 판단하는 것은 visited 배열이다. depth가 추가될 때 마다 visited의 true 개수는 하나씩 늘어날 것이다. depth가 n/2과 같아지는 시점에 정확히 팀이 나눠질 것이고 나눠진 팀을 기반으로 능력치의 차이값을 구한다.

 

해당 작업이 완료되면 재귀가 완료되고 다른 경우를 찾기 위해 visited를 false로 바꿔준다. 이러한 과정을 거치며 두 팀 사이의 최솟값을 지속적으로 갱신해준다.

 

한 가지 주의해야 할 점은 for loop를 수행하고 combination을 재귀호출할 때 start 인자로 i 다음 차례인 i + 1을 넘겨야 한다. 예를 들어 n이 8일 때 1, 3까지 팀이 꾸려졌다고 가정하면 앞으로 2명의 선수를 더 영입할 수 있다. 다음으로 올 수 있는 선수는 4 이상 부터 가능하기 때문이다. 예를들면 (1, 3, 4, 5), (1, 3, 4, 6) 등이 올 수 있다. (1, 3, 2, 4)와 같은 형태는 허용하지 않는다.

 

private static int getDifference() {
    int sumByStartTeam = 0;
    int sumByLinkTeam = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (visited[i] && visited[j]) sumByStartTeam += s[i][j];
            if (!visited[i] && !visited[j]) sumByLinkTeam += s[i][j];
        }
    }

    return Math.abs(sumByStartTeam - sumByLinkTeam);
}

 

작성한 vistied를 기반으로 startTeam과 linkTeam의 능력치를 합산하고 둘 사이의 최솟값을 반환한다.

 

밑은 전체 코드이다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Baekjoon14889 {

    static int[][] s; // 능력치 저장을 위한 이차배열
    static boolean[] visited; // 선수들의 명단 체크를 위한 boolean 배열
    static int n;
    static int min = Integer.MAX_VALUE;

    private static void combination(int start, int depth) {
        if (depth == n / 2) {
            min = Math.min(min, getDifference());
            return;
        }

        for (int i = start; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                combination(i + 1, depth + 1);
                visited[i] = false;
            }
        }
    }

    private static int getDifference() {
        int sumByStartTeam = 0;
        int sumByLinkTeam = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (visited[i] && visited[j]) sumByStartTeam += s[i][j];
                if (!visited[i] && !visited[j]) sumByLinkTeam += s[i][j];
            }
        }

        return Math.abs(sumByStartTeam - sumByLinkTeam);
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for (int i = 1; i <= n; i++) {
            String[] input = bufferedReader.readLine().split(" ");
            for (int j = 1; j <= n; j++) {
                s[i][j] = Integer.parseInt(input[j - 1]);
            }
        }

        combination(1, 0);
        bufferedWriter.write(String.valueOf(min));

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}