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

문제 URL

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

나의 풀이

package backjoon;

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] s;
    static int[] team1;
    static int[] team2;
    static int ans = Integer.MAX_VALUE;

    public static void main(String args[]) throws IOException {
        StringTokenizer str = new StringTokenizer(br.readLine());
        int size = Integer.parseInt(str.nextToken());
        team1 = new int[size / 2];
        team2 = new int[size / 2];
        s = new int[size + 1][size + 1];
        for (int i = 1; i <= size; i++) {
            str = new StringTokenizer(br.readLine());
            for (int j = 1; j <= size; j++) {
                s[i][j] = Integer.parseInt(str.nextToken());
            }
        }

        go(1, 0, 0, size);
        System.out.println(ans);
        bw.flush();
        bw.close();
    }

    public static void go(int idx, int selected1, int selected2, int m) {
        if (selected1 == m / 2 && selected2 == m / 2) {
            int sum1 = 0, sum2 = 0;
            //능력치 계산
            for (int i = 0; i < m / 2; i++) {
                for (int j = i + 1; j < m / 2; j++) {
                    sum1 += s[team1[i]][team1[j]] + s[team1[j]][team1[i]];
                    sum2 += s[team2[i]][team2[j]] + s[team2[j]][team2[i]];
                }
            }
            int n = Math.abs(sum1-sum2);
            if (n < ans)
                ans = n;
            return;
        }
        if (idx > m)
            return;

        // index번째 사람을 team1에 넣는경우
        if (selected1 < m / 2) {
            team1[selected1] = idx;
            go(idx + 1, selected1 + 1, selected2, m);
        }
        // index번째 사람을 team1에 넣는경우
        if (selected2 < m / 2) {
            team2[selected2] = idx;
            go(idx + 1, selected1, selected2 + 1, m);
        }
    }
}

다른 풀이

import java.util.*;
public class Main {
    static int[][] s;
    static int n;
    static int go(int index, ArrayList<Integer> first, ArrayList<Integer> second) {
        if (index == n) {
            if (first.size() != n/2) return -1;
            if (second.size() != n/2) return -1;
            int t1 = 0;
            int t2 = 0;
            for (int i=0; i<n/2; i++) {
                for (int j=0; j<n/2; j++) {
                    if (i == j) continue;
                    t1 += s[first.get(i)][first.get(j)];
                    t2 += s[second.get(i)][second.get(j)];
                }
            }
            int diff = Math.abs(t1-t2);
            return diff;
        }
        int ans = -1;
        first.add(index);
        int t1 = go(index+1, first, second);
        if (ans == -1 || (t1 != -1 && ans > t1)) {
            ans = t1;
        }
        first.remove(first.size()-1);
        second.add(index);
        int t2 = go(index+1, first, second);
        if (ans == -1 || (t2 != -1 && ans > t2)) {
            ans = t2;
        }
        second.remove(second.size()-1);
        return ans;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                s[i][j] = sc.nextInt();
            }
        }
        ArrayList<Integer> first = new ArrayList<>();
        ArrayList<Integer> second = new ArrayList<>();
        System.out.println(go(0, first, second));
    }
}

다른 풀이(개선) **

백트래킹을 활용한 풀이 다른풀이1과 다르게 모든 경우를 탐색하지않는다. 불가능한 경우인 first의 크기 > n/2 또는 second의 크기 > n/2 이면 더이상 탐색하지않는다.

import java.util.*;
public class Main {
    static int[][] s;
    static int n;
    static int go(int index, ArrayList<Integer> first, ArrayList<Integer> second) {
        if (index == n) {
            if (first.size() != n/2) return -1;
            if (second.size() != n/2) return -1;
            int t1 = 0;
            int t2 = 0;
            for (int i=0; i<n/2; i++) {
                for (int j=0; j<n/2; j++) {
                    if (i == j) continue;
                    t1 += s[first.get(i)][first.get(j)];
                    t2 += s[second.get(i)][second.get(j)];
                }
            }
            int diff = Math.abs(t1-t2);
            return diff;
        }
        //불가능한 경우 더이상 탐색 x
        if (first.size() > n/2) return -1;
        if (second.size() > n/2) return -1;
        int ans = -1;
        first.add(index);
        int t1 = go(index+1, first, second);
        if (ans == -1 || (t1 != -1 && ans > t1)) {
            ans = t1;
        }
        first.remove(first.size()-1);
        second.add(index);
        int t2 = go(index+1, first, second);
        if (ans == -1 || (t2 != -1 && ans > t2)) {
            ans = t2;
        }
        second.remove(second.size()-1);
        return ans;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                s[i][j] = sc.nextInt();
            }
        }
        ArrayList<Integer> first = new ArrayList<>();
        ArrayList<Integer> second = new ArrayList<>();
        System.out.println(go(0, first, second));
    }
}

느낀점

방법의수: 2의 n제곱 문제의 크기 4<=N<=20 이므로 브루트포스로 풀이가 가능하다.

---