[백준] 14889번 - 스타트와 링크

문제 >

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

 

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

 

입력 >

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

 

출력 >

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

 

해결방법 > 

DFS(깊이우선탐색)으로 문제 해결.

 

1) 깊이 우선 탐색으로 N명을  2개의 팀으로 나누는 경우를 모두 찾는다.

 

2) 1)과정에서 2팀으로 나눈 경우를 찾을 때마다, 양 팀의 능력치 차이를 구한다.

 

3) 능력치 차이가 이전에 구했던 능력치 차이보다 작을 경우 저장한다.

 

아래 구현 코드에서 첫번째 소스코드는 한 정점을 시작으로 깊이우선탐색을 진행하는 코드이다.

 

시간 초과가 되었다. 프루닝조건을 아무리 찾아도 생각나지가 않았다.

 

그래서 각 원소를 포함하는 경우, 포함하지 않는 경우로 깊이우선탐색을 했다.(두번째 소스코드)

 

이전에 구현했던 코드가 민망할 정도로 그냥 통과해버렸다.

 

하지만, 실행시간이 조금 걸리는 것 같아서 두가지 조건을 추가했다.

 

1. 최소값이 0이 구해졌다면 탐색을 종료한다.

(절대값의 최소값은 0이므로)

 

2. 현재 탐색하고 있는 인덱스에서 포함하고있는 수와 남은 원소의 수의 합이 총 원소의 개수가 반이 되지 않으면 탐색을 하지않는다.

(각 팀은 반으로 나누어져야하므로)

 

[JAVA]

import java.util.*;

public class Main {
	static int n;
	static int[] visit;
	static int[][] a;
	static int min;
	
	public static void dfs(int s, int x, int depth) {
		visit[x] = 1;
		if(depth == n/2 - 1) {
			score();
			visit[x] = 0;
			return;
		}
		
		for(int i = s; i < n; i++) {
			if(visit[i] == 0 && (depth + (n-i)) >= n/2) {
				dfs(s, i, depth + 1);
			}
		}
		visit[x] = 0;
	}
	
	public static void score() {
		int one = 0;
		int two = 0;
		for(int i = 0; i < n; i++) {
			if(visit[i] == 1) {
				for(int j = 0; j < n; j++) {
					if(visit[j] == 1) {
						one += a[i][j];
					}
				}
			}
			if(visit[i] == 0) {
				for(int j = 0; j < n; j++) {
					if(visit[j] == 0) {
						two += a[i][j];
					}
				}
			}
		}
		min = Math.min(min, Math.abs(one-two));
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		a = new int[n][n];
		visit = new int[n];
		min = 20000;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				a[i][j] = sc.nextInt();
			}
		}
		for(int i = 0; i < n/2; i++) {
			dfs(i, i, 0);
		}
		
		System.out.println(min);
	}
}

 

package baekjoon;

import java.util.*;

public class s_14889 {
	static int n;
	static int[] visit;
	static int[][] a;
	static int min;
	
	public static void dfs(int idx, int flag, int depth, int[] visit) {
		int[] arr = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = visit[i];
		}
		
		arr[idx] = flag;
		if(depth == n/2) {
			score(arr);
			return;
		}
		if(n-idx+depth < n/2 || idx == n - 1 || min == 0) return;
		dfs(idx+1, 0, depth, arr);
		dfs(idx+1, 1, depth+1, arr);
	}
	
	public static void score(int[] visit) {
		int one = 0;
		int two = 0;
		for(int i = 0; i < n; i++) {
			if(visit[i] == 1) {
				for(int j = 0; j < n; j++) {
					if(visit[j] == 1) {
						one += a[i][j];
					}
				}
			}
			if(visit[i] == 0) {
				for(int j = 0; j < n; j++) {
					if(visit[j] == 0) {
						two += a[i][j];
					}
				}
			}
		}
		min = Math.min(min, Math.abs(one-two));
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		a = new int[n][n];
		visit = new int[n];
		min = 20000;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				a[i][j] = sc.nextInt();
			}
		}
		
		dfs(0, 0, 0, visit);
		dfs(0, 1, 1, visit);
		
		System.out.println(min);
	}
}