[JAVA] 백준 (실버1) 14889번 스타트와 링크

링크

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

---

문제 설명

정답률 46.115%

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다.

---

입력 예제

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

---

출력 예제

0

---

풀이

N명이 있을 때 N/2명씩 두 팀을 뽑을 때 능력치의 차이가 최소가 될 때를 구해야 한다. 모든 인덱스에 대해 반복하면서 방문하지 않았을 경우 카운트, 즉 재귀를 호출한다.

for (int i = index; i < N; i++) {
    if (!visited[i]) {
        visited[i] = true;
        combination(i + 1, count + 1);
        visited[i] = false;
    }
}

재귀의 깊이인 count가 N/2가 되면 팀의 능력치 차이를 계산한 뒤 반환한다.

//N/2명의 팀을 뽑았을 경우 리턴
if (count == N / 2) {
    //팀의 능력치의 차이를 계산
    diff();
    return;
}

팀의 능력치는 모든 인덱스에 대해 반복하면서 방문한 인덱스와 아닌 인덱스로 구분한다.

for (int i = 0; i < N - 1; i++) {
    for (int j = i + 1; j < N; j++) {
        //방문했으면 팀 A로 계산
        if (visited[i] && visited[j]) {
            teamA += ability[i][j] + ability[j][i];
        }
        //방문하지 않았으면 팀 B로 계산
        else if (!visited[i] && !visited[j]) {
            teamB += ability[i][j] + ability[j][i];
        }
    }
}

코드

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

//백준
public class Main {

    static int min = Integer.MAX_VALUE;
    static int N;
    static int[][] ability;
    static boolean[] visited;

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

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        ability = new int[N][N];
        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            ability[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
        }

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

    static void combination(int index, int count) {
        //N/2명의 팀을 뽑았을 경우 리턴
        if (count == N / 2) {
            //팀의 능력치의 차이를 계산
            diff();
            return;
        }

        for (int i = index; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                combination(i + 1, count + 1);
                visited[i] = false;
            }
        }

    }

    static void diff() {

        int teamA = 0;
        int teamB = 0;

        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                //방문했으면 팀 A로 계산
                if (visited[i] && visited[j]) {
                    teamA += ability[i][j] + ability[j][i];
                }
                //방문하지 않았으면 팀 B로 계산
                else if (!visited[i] && !visited[j]) {
                    teamB += ability[i][j] + ability[j][i];
                }
            }
        }

        int var = Math.abs(teamA - teamB);
        //차이가 0이면 출력 후 종료
        if (var == 0) {
            System.out.println(var);
            System.exit(0);
        }

        min = Math.min(var, min);
    }
}