[BOJ-Silver1] 14889번 스타트와 링크

💡 첫번째 풀이

• 조합 알고리즘 사용해서 start에 속한 팀원의 번호를 n/2개씩 뽑기
• visited[i]를 확인해서 각각의 ArrayList에 팀원 번호 넣기
• 팀원 번호 하나씩 빼서 link와 start팀 각각 능력치 계산 후 차이 중 작은 값 담기

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;
	static int[][] arr;
	static boolean[] visited;
	static int result = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[n][n];
		visited = new boolean[n];
		for(int i = 0; i<n; i++){
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j<n ; j++){
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		combination(0, 0, n/2);
		System.out.println(result);
	}

	public static void combination(int start, int depth, int num){
		if (depth == num){
			ArrayList<Integer> startTeam = new ArrayList<>();
			ArrayList<Integer> linkTeam = new ArrayList<>();

			for(int i = 0; i<n; i++){
				if (visited[i])
					startTeam.add(i);
				else
					linkTeam.add(i);
			}

			int startSum = 0;
			int linkSum = 0;
			for (int i = 0; i<num; i++){
				for(int j = i+1; j<num; j++){
					int a = startTeam.get(i);
					int b = startTeam.get(j);
					startSum += arr[a][b] + arr[b][a];

					a = linkTeam.get(i);
					b = linkTeam.get(j);
					linkSum += arr[a][b] + arr[b][a];
				}
			}
			result = Integer.min(result, Math.abs(startSum - linkSum));
			return;
		}

		for(int i = start; i<n; i++){
			if (!visited[i]){
				visited[i] = true;
				combination(i+1, depth+1, num);
				visited[i] = false;
			}
		}
	}
}

💡 리팩토링 풀이

• 위에 코드에서 arrayList를 두번 쓰는게 별로여서 리팩토링함
• arrayList에 담지 않고 depth가 해당 n/2에 도달하면 getDiff 함수 실행 후 최솟값 갱신
• getDiff 함수는 i와 j를 돌면서 visited가 true인 애들끼리 start에 더하고 false인 애들끼리 link에 더해서 두 팀의 차이 계산 후 반환

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

public class Main {
	static int n;
	static int[][] arr;
	static boolean[] visited;
	static int result = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[n][n];
		visited = new boolean[n];
		for(int i = 0; i<n; i++){
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j<n ; j++){
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		combination(0, 0, n/2);
		System.out.println(result);
	}

	public static void combination(int start, int depth, int num){
		// 해당 depth가 n / 2에 도달하면 result 계산 후 리턴
		if (depth == num){
			result = Math.min(result, getDiff());
			return;
		}

		for(int i = start; i<n; i++){
			if (!visited[i]){
				visited[i] = true;
				combination(i+1, depth+1, num);
				visited[i] = false;
			}
		}
	}
	
	public static int getDiff(){
		int start = 0;
		int link = 0;
		for(int i = 0; i<n; i++){
			for(int j = 0; j<n; j++){
				// i랑 j가 같으면 넘어가기
				if (i == j) continue;

				// visited가 true인 애들끼리 start에 능력치 더하기
				if (visited[i] && visited[j]) start += arr[i][j];
				if (!visited[i] && !visited[j]) link += arr[i][j];
			}
		}
		return Math.abs(start - link);
	}
}