21.05.29 - [BOJ] 15661. 링크와 스타트

[suhyunsim]

문제

• 15661

핵심 아이디어

• 스타트와 링크에서 인원수 제한 조간이 빠진 문제

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q15661;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int n;
    static int[][] s;

    private static int go(int index, ArrayList<Integer> first, ArrayList<Integer> second) {
        if (index == n) {
            if (first.size() == 0) return -1;
            if (second.size() == 0) return -1;
            int t1 = 0;
            int t2 = 0;
            for (int i = 0; i < first.size(); i++) {
                for (int j = 0; j < first.size(); j++) {
                    if (i == j) continue;
                    t1 += s[first.get(i)][first.get(j)];
                }
            }
            for (int i = 0; i < second.size(); i++) {
                for (int j = 0; j < second.size(); j++) {
                    if (i == j) continue;
                    t2 += s[second.get(i)][second.get(j)];
                }
            }
            return Math.abs(t1 - t2);
        }
        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));
    }
}