백준 14889번 스타트와 링크 - DFS, 백트래킹

문제 개요

https://www.acmicpc.net/problem/14889

N명이 있을 때, 두 팀으로 나누어 능력치의 차이가 최소가 되도록 팀을 나누는 문제입니다. 각 팀의 능력치는 팀 내 두 사람 간의 시너지의 합으로 계산됩니다. 단, 반드시 두 팀은 N/2명으로 균등하게 나누어야 합니다.

---

전체 코드

package baekjoon;

import java.util.*;

public class Main {
	static boolean[] team;
	static int[][] power;
	static int n, answer = Integer.MAX_VALUE;

	public static void DFS(int L, int idx) {
		if (L == n / 2) {
			int startTeam = 0;
			int linkTeam = 0;

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (i == j) continue;
					if (team[i] && team[j]) startTeam += power[i][j];
					if (!team[i] && !team[j]) linkTeam += power[i][j];
				}
			}

			answer = Math.min(answer, Math.abs(startTeam - linkTeam));
		} else {
			for (int i = idx; i < n; i++) {
				team[i] = true;
				DFS(L + 1, i + 1);
				team[i] = false;
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();

		power = new int[n][n];
		team = new boolean[n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				power[i][j] = sc.nextInt();
			}
		}

		DFS(0, 0);
		System.out.print(answer);
		sc.close();
	}
}

---

코드 설명

main 함수

• n명의 사람에 대한 정보를 입력받고, power[i][j]는 i번 사람과 j번 사람이 같은 팀일 때 발생하는 시너지(능력치)를 나타냅니다.
• 팀 조합을 탐색하기 위해 DFS(0, 0) 호출로 시작합니다.

DFS 함수

public static void DFS(int L, int idx)

• L: 현재 팀에 속한 인원 수
• idx: 현재 탐색 시작 인덱스

기저 조건

if (L == n / 2)

• 팀이 정확히 절반(n/2) 구성되면 두 팀의 능력치를 각각 계산하고 차이를 구합니다.
• 각 팀 내의 모든 조합에 대해 power[i][j]를 더하며 시너지를 계산합니다.

---

백트래킹 탐색

for (int i = idx; i < n; i++) {
    team[i] = true;
    DFS(L + 1, i + 1);
    team[i] = false;
}

• 인덱스 idx 이후부터 탐색하며 팀을 구성합니다.
• 탐색 후에는 다시 상태를 되돌려 다음 조합을 탐색합니다. (백트래킹)

---

시간 복잡도 분석

• 전체 인원의 조합을 구하는 방식이므로 시간 복잡도는 O(nCr) = O(n! / ((n/2)! * (n/2)!))
• 최대 n = 20이므로 10명씩 나누는 경우만 탐색하면 되며 완전탐색이 가능한 범위입니다.