[BOJ] 14889. 스타트와 링크- Permutation

[BOJ] 14889. 스타트와 링크- Permutation

제출일 : 2019-10-14

문제 풀이 시간 : 40M

난이도 : ★★

Problem

link : https://www.acmicpc.net/problem/148989

Input

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

Output

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

Example

input

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

output

0

Solution & Inpression

N개중 N/2개를 선택하여 2개의 그룹으로 나눈뒤 각각의 그래프의 가중치를 더해 최솟값을 찾는 문제. [BOJ]게리멘더링을 풀기전에 풀어보았더라면 게리멘더링을 더 쉽게 풀었을것 같다.

Code

언어 : JAVA

메모리 : 17,560kb

실행시간 : 336 ms

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[][] matrix;
    static int[] visit;
    static int min;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        min = Integer.MAX_VALUE;
        visit = new int[N];
        solve(N, N / 2, 0, 0);
        System.out.println(min);

    }

    static void solve(int n, int r, int depth, int start) {
        if(depth!=0&&visit[0]==0)
            return;
        if (depth == r) {
            int team1 = 0, team2 = 0;
            //System.out.println(Arrays.toString(visit));
            for (int i = 0; i < n; i++) {
                if (visit[i] == 1)
                    for (int j = 0; j < n; j++) {
                        if (i != j && visit[j] == 1)
                            team1 += matrix[i][j];
                    }
                else
                    for (int j = 0; j < n; j++) {
                        if (i != j && visit[j] == 0)
                            team2 += matrix[i][j];
                    }
            }
            int res = Math.abs(team1 - team2);
            if (res < min)
                min = res;
            return;
        }

        for (int i = start; i < n; i++) {
            if (visit[i] == 0) {
                visit[i] = 1;
                solve(n, r, depth + 1, i);
                visit[i] = 0;
            }
        }
    }
}