SWEA_4012

📁 [SWEA_4012] 요리사

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution{
	static StringTokenizer st;
	static int[][] arr;
	static boolean[] visited;
	static int N;
	static int min;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		// 테스트 케이스 수
		int tc = Integer.parseInt(br.readLine());

		for (int T = 1; T <= tc; T++) {
			sb.append("#").append(T).append(" ");
			min = Integer.MAX_VALUE;

			// N 개수
			N = Integer.parseInt(br.readLine());

			arr = new int[N][N];
			visited = new boolean[N];
			

			// 배열 입력
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());

				}
			}
			
			combination(0,0);
			sb.append(min).append("\n");
		}
		System.out.println(sb);
	}

	// 조합계산
	static void combination(int cnt, int start) {
		if (cnt == N / 2) {
			check();
			return;
		}

		for (int i = start; i < N; i++) {
			visited[i] = true;
			combination(cnt + 1, i + 1);
			visited[i] = false;
		}
	}
		
	static void check() {
		int A = 0;
		int B = 0;
		int result = 0;
		
		for(int i=0; i<N-1; i++) {
			for(int j = i+1; j<N; j++) {
				if(visited[i] && visited[j]) {
					A+=arr[i][j]+arr[j][i];
				}
				else if(!visited[i] && !visited[j]) {
					B+=arr[i][j]+arr[j][i];
				}
			}
		}
		result = Math.abs(A-B);
		min = Math.min(result, min);
		
	}
}

🤔 나의 생각