SWEA 4012 요리사 (Java)

식재료들을 각각 N / 2개씩 나누어 두 개의 요리를 하려고 한다. (N은 짝수이다.)
식재료 i를 식재료 j와 같이 요리하게 되면 발생하는 시너지 Sij의 정보가 주어지고,
가지고 있는 식재료를 이용해 A음식과 B음식을 만들 때,
두 음식 간의 맛의 차이가 최소가 되는 경우를 찾고
그 최솟값을 정답으로 출력하는 프로그램을 작성하라.

재귀와 반복문을 이용한 DFS & 방문체크

• Java

import java.util.Scanner;

class Solution {
    static int N, mini;		// 식재료 수, 맛 차이 최솟값
    static int[][] S;		// 음식 시너지
    static boolean[] check;	// 방문체크
    
	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		int T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++) {
			N = sc.nextInt();
            S = new int[N][N];
            check = new boolean[N];
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                	S[i][j] = sc.nextInt();
                    mini += S[i][j];		// 최댓값으로 초기화
                }
            }
            dfs(0, 0);
            System.out.println("#" + test_case + " " + mini);
		}
	}
    static void dfs(int cnt, int idx) {
        if(cnt == N / 2) {							// 식재료 절반 골랐으면
            int sum1 = 0, sum2 = 0;
            for(int i = 0; i < N; i++) {
            	for(int j = i + 1; j < N; j++){
                	if(check[i] && check[j]) {
                    	sum1 += S[i][j] + S[j][i]; // 고른 식재료로 만든 음식
                    } else if(!check[i] && !check[j]) {
                    	sum2 += S[i][j] + S[j][i]; // 나머지 식재료로 만든 음식
                    }
                }
            } // end for i
            int diff = Math.abs(sum1 - sum2);	// 맛의 차이
            mini = Math.min(mini, diff);		// 최솟값 비교
            return;
        }
        for(int i = idx; i < N; i++) {
            check[i] = true;
			dfs(cnt+1, i+1);
            check[i] = false;
        }
    }
}