백준 14889 스타트와 링크[Java]

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

풀이

DFS를 사용하여 팀을 만들 수 있는 모든 경우를 탐색한 다음 최솟값을 구한다. 이 때 조합을 사용하여 모든 조합의 경우의 수를 탐색하고, 구분은 boolean[] check 배열을 사용한다.

코드

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

public class Main {

    static int n, answer = Integer.MAX_VALUE;
    static int[][] s;
    static boolean[] check;

    public static void comb(int L, int start) {
        if (L == n/2) {
            int st = 0, link = 0;

            for (int i = 0; i < n; i++){
                for (int j = 0; j < n; j++) {
                    if (check[i] && check[j])
                        st += s[i][j];
                    else if (!check[i] && !check[j])
                        link += s[i][j];
                }
            }

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

        for (int i = start; i < n; i++) {
            check[i] = true;
            comb(L+1, i+1);
            check[i] = false;
        }

    }


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        s = new int[n][n];
        check = new boolean[n];

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

        comb(0, 0);
        System.out.println(answer);
    }
}

• 조합을 만드는 재귀함수를 사용한다.
• L == n/2이면 팀이 만들어졌으므로 이중 for문을 사용해 각 팀의 능력치 합을 구한다.
• 두 팀의 능력치 차이의 최솟값을 answer에 저장한다.

---

다른 풀이

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

public class Main {

    static int n, answer = Integer.MAX_VALUE;
    static int[][] s;
    static boolean[] check;

    public static void comb(int L, int start) {
        if (L == n/2) {
            int st = 0, link = 0;

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

            answer = Math.min(answer, Math.abs(st-link));

            if (answer == 0) {
                System.out.println(0);
                System.exit(0);
            }

            return;
        }

        for (int i = start; i < n; i++) {
            check[i] = true;
            comb(L+1, i+1);
            check[i] = false;
        }

    }


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        s = new int[n][n];
        check = new boolean[n];

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

        comb(0, 0);
        System.out.println(answer);
    }
}

• s[i][j], s[j][i]를 한 번에 더하기 위해서는 대각선을 기준으로 위쪽 구역만 탐색하면 된다.
• answer 값이 0이면 답이 될 수 있는 가장 최솟값이므로 System.exit(0)을 호출해 프로그램을 종료한다.

참고: https://st-lab.tistory.com/122?category=862595

첫번째 방법이 더 근소하게 메모리와 시간을 적게 쓴다.