[SWEA 4012번] 요리사 :: 늦깎이 IT

[4012. [모의 SW 역량테스트] 요리사 URL]

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH&categoryId=AWIeUtVakTMDFAVH&categoryType=CODE

백준의 스타트와 링크 문제와 100% 같은 문제이다.

2019/03/09 - [알고리즘 문제/백준(BOJ)] - [백준 14889번] 스타트와 링크 (JAVA)

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Solution {
 
    public static int tCase, N, ans;
    public static int[][] map;
    public static boolean[] selectFood;
    public static int[] dirX = new int[] { 0, 0, 1, -1 }; // 동서남북
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        tCase = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= tCase; t++) {
 
            ans = Integer.MAX_VALUE;
            N = Integer.parseInt(br.readLine());
            selectFood = new boolean[N];
            map = new int[N][N];
 
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            dfs(0, 0);
            System.out.println("#" + t + " " + ans);
        }
    }
 
    public static void dfs(int depth, int numOfFood) {
 
        if (depth >= N)
            return;
 
        if (numOfFood == N / 2) {
            List<Integer> A = new ArrayList<>();
            List<Integer> B = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                if (selectFood[i])
                    A.add(i);
                else
                    B.add(i);
            }
            int a = 0, b = 0;
            for (int i = 0; i < A.size() - 1; i++) {
                for (int j = i + 1; j < A.size(); j++) {
                    a += map[A.get(i)][A.get(j)];
                    b += map[B.get(i)][B.get(j)];
                    a += map[A.get(j)][A.get(i)];
                    b += map[B.get(j)][B.get(i)];
                }
            }
            ans = Math.min(ans, Math.abs(a - b));
            return;
        }
 
        selectFood[depth] = true;
        dfs(depth + 1, numOfFood + 1);
 
        selectFood[depth] = false;
        dfs(depth + 1, numOfFood);
 
    }
 
}