풀이

아이디어

단순하게 생각하면 스타트에 선택된 사람들과 선택되지 않은 사람들을 따로 분류해서 계산하면 되는 문제이다.

구현의 단계를 쉽게 나눠보자

1. DFS로 조합을 만들어서 스타트팀과 스타트팀에 속하지 않은 팀을 구한다.

2. 각 팀(스타트 팀, 링크 팀)의 점수를 계산한다.

3. 최소의 값을 찾아서 저장, 출력한다.

상세구현

1. DFS로 조합 구현

DFS로 조합을 구현하는 방법은 많이 경험할 수 있습니다! 이 문제의 경우에는 N과 M(6)과 같은 경우입니다.
https://www.acmicpc.net/problem/15655
조합문제이며 자신을 포함하지 않아야 하며 중복 문제를 해결하기 위해 오름차순으로 해결해야 합니다.

선택 여부는 boolean 배열을 이용하여 방문 여부를 기록하는 것이 대부분이지만 이 문제의 경우 비트마스킹을 이용하여 현재 방문한 자릿수를 저장하였습니다.

		dfs(0, 0);
//---------중략------------//
	private static void dfs(int start, int bit) {
    	// 현재 선택된 애들이 기록된 bit를 가지고 
		// Start와 Link팀의 점수를 계산
		check(bit);
		
		for(int i=start; i<N; i++) {
			bit += (1<<i);
			dfs(i+1, bit);
			bit -= (1<<i);
		}
	}

2. 이제 bit를 가지고 각 팀의 점수를 계산해 봅시다.

전달된 bit를 한번 출력해서 내용을 보겠습니다.

11이란 bit가 왔는데요. 이 비트는 무엇을 의미할까요? 이게 왜 방문 여부를 기록해주고 있을까요?

이는 11을 2진수로 표현하면 쉽게 보입니다. 11은 이진수로 1011인데 이걸 보면 아! 하고 생각이 드실겁니다. 1이라고 표현된 자리가 Start팀에 속해 있는거죠!

0, 1, 3이 Start 팀
2가 Link 팀

이런 식으로 기록이 된 숫자들을 2중 for문을 통해서 같은 팀에 포함된 선수인 경우를 찾아 값을 더해주면 됩니다.

		int start = 0, link = 0;
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(((1 <<i) & bit) > 0 && ((1<<j) & bit) > 0) {
					start += mat[i][j];
				}else if(((1<<i) & bit) <= 0 && ((1<<j) & bit) <= 0) {
					link += mat[i][j];
				}
			}
		}

3. 최소의 값을 저장

		min = Math.min(min, Math.abs(start - link));

이제 이 값을 마지막에 출력하면 문제는 해결이 됩니다.

코드

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

public class No15661 {
	static int N, min;
	static int[][] mat;
	public static void main(String[] args) throws IOException {
		input();
		pro();
	}
	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		mat = new int [N][N];
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				mat[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		br.close();
	}
	private static void pro() {
		min = Integer.MAX_VALUE;
		dfs(0, 0);
		System.out.println(min);
	}
	private static void dfs(int start, int bit) {
		// 현재 선택된 애들이 기록된 bit를 가지고 
		// Start와 Link팀의 점수를 계산
		check(bit);
		
		for(int i=start; i<N; i++) {
			bit += (1<<i);
			dfs(i+1, bit);
			bit -= (1<<i);
		}
	}
	private static void check(int bit) {
		int start = 0, link = 0;
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(((1 <<i) & bit) > 0 && ((1<<j) & bit) > 0) {
					start += mat[i][j];
				}else if(((1<<i) & bit) <= 0 && ((1<<j) & bit) <= 0) {
					link += mat[i][j];
				}
			}
		}
		min = Math.min(min, Math.abs(start - link));
	}
}