[백준] 15661. 링크와 스타트 (Java)

 

문제

15661번: 링크와 스타트

 

알고리즘

브루트포스

 

풀이

두 팀으로 나뉘어지므로 한 팀에 속할 인원을 구하면 다른 팀도 구할 수 있다.

팀원은 제한이 없으므로 각 인원이 팀1에 속하거나 속하지 않는 2가지 선택지를 갖는 부분집합 문제이다.

N이 최대 20이므로 경우의 수는 2^20 = 약 100만이다.

 

팀1에 속할 인원의 부분집합을 구하고, 팀1에 속하지 않은 인원을 팀2에 넣은 후

팀1과 팀2의 시너지 합을 구해 차이를 최솟값과 비교해 갱신하면 된다.

 

코드

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

public class Main {
	static int N, power[][], min;
	static boolean selected[];

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

		N = Integer.parseInt(br.readLine());
		power = new int[N][N];
		selected = new boolean[N];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				power[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		min = Integer.MAX_VALUE;
		powerSet(0);

		System.out.println(min);
	}

	private static void powerSet(int count) {

		if (count == N) {
			ArrayList<Integer> team1 = new ArrayList<>();
			ArrayList<Integer> team2 = new ArrayList<>();

			for (int i = 0; i < N; i++) {
				if (selected[i]) team1.add(i);
				else team2.add(i);
			}

			int sum1 = 0;
			int sum2 = 0;

			for (int i = 0; i < team1.size(); i++)
				for (int j = i + 1; j < team1.size(); j++)
					sum1 += power[team1.get(i)][team1.get(j)] + power[team1.get(j)][team1.get(i)];

			for (int i = 0; i < team2.size(); i++)
				for (int j = i + 1; j < team2.size(); j++)
					sum2 += power[team2.get(i)][team2.get(j)] + power[team2.get(j)][team2.get(i)];

			min = Math.min(min, Math.abs(sum1 - sum2));
			return;
		}

		selected[count] = true;
		powerSet(count + 1);

		selected[count] = false;
		powerSet(count + 1);
	}
}