설명
풀이 흐름 설명
이 문제는 단순히 모든 경우를 이중 반복문으로 계산하는 브루트포스 문제가 아니었다.
핵심은 N명을 정확히 N/2명씩 두 팀으로 나누는 것이며 이는 조합 문제에 해당한다.따라서 한 팀을 구성하는 모든 경우의 수를 구한 뒤 나머지 인원은 자동으로 상대 팀이 되도록 처리하였다. 이를 위해 백트래킹을 사용하여 N명 중 N/2명을 선택하는 조합을 생성하였다.
DFS 함수는 다음과 같은 흐름으로 구성하였다.
- depth가 N/2에 도달하면 팀 구성이 완료된 것이므로 능력치 계산을 수행하였다.
- 현재 인덱스(start)부터 N까지 반복하면서 아직 선택되지 않은 인원을 선택하였다.
3.선택 후 재귀 호출을 진행하고 호출이 끝나면 다시 선택을 취소하여 다음 경우를 탐색하였다.- 이 과정을 통해 중복 없이 모든 조합을 탐색하였다.
계산 과정 설명
팀이 완성되면 능력치 차이를 계산하였다.
check[i] == true 인 경우를 A팀
check[i] == false 인 경우를 B팀이후 i < j 범위에서 반복문을 돌며
두 명 모두 true이면 A팀 능력치에 더하고
두 명 모두 false이면 B팀 능력치에 더하였다.이렇게 하면 한 쌍을 두 번 더하는 문제를 방지할 수 있다.
각 조합에 대해 두 팀의 능력치 차이의 절댓값을 구하고 그 중 최솟값을 갱신하였다.조합으로 접근해야 하는 이유
이 문제에서 중요한 점은 “순서”가 아니라 “선택”이라는 점이다.
예를 들어 1번과 2번을 뽑는 경우와 2번과 1번을 뽑는 경우는 동일한 팀 구성이다.
따라서 순열이 아닌 조합으로 접근해야 한다.이를 위해 DFS에서 반복문의 시작점을 start로 설정하였다.
재귀 호출 시 i + 1을 넘겨주어 이미 고려한 인덱스는 다시 선택하지 않도록 하였다.
이 방식이 바로 조합을 생성하는 전형적인 백트래킹 패턴이다.방문 배열에 대한 고민과 해결
처음에는 팀 구성이 2개이므로 방문 배열을 2차원으로 만들어야 하는지 고민하였다.
하지만 실제로는 각 사람이 어느 팀에 속하는지만 알면 되므로 1차원 boolean 배열이면 충분하였다.true → A팀
false → B팀
으로 해석하면 나머지 팀은 자동으로 결정되기 때문이다.
따라서 추가적인 2차원 구조는 필요하지 않았다.백트래킹이 실제로 어떻게 진행되는지 예시로 따라가기
예를 들어 N=6이고 능력치 배열이 아래와 같다고 가정하자.
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0이제 N=6이므로 한 팀은 3명씩 구성해야 한다.
check[i] = true는 A팀, false는 B팀을 의미한다.
초기 상태는 다음과 같다.
check = [false, false, false, false, false, false, false]
(0번 인덱스는 사용하지 않음)depth = 0, start = 1
1️⃣ 첫 번째 DFS 진행i=1 선택
check[1] = true
현재 상태:
[ -, true, false, false, false, false, false ]재귀 호출 → depth=1, start=2
2️⃣ 두 번째 선택
i=2 선택
check[2] = true
현재 상태:
[ -, true, true, false, false, false, false ]재귀 호출 → depth=2, start=3
3️⃣ 세 번째 선택
i=3 선택
check[3] = true
현재 상태:
[ -, true, true, true, false, false, false ]depth == 3 (N/2) 이므로 팀 완성.
이때 팀 구성은?
A팀: {1, 2, 3}
B팀: {4, 5, 6}이제 calculate()가 실행된다.
능력치 계산 방식
반복문은 i < j 범위에서만 돈다.
예를 들어 A팀 내부 계산은
(1,2)
(1,3)
(2,3)
만 계산한다.arr[1][2] + arr[2][1]
arr[1][3] + arr[3][1]
arr[2][3] + arr[3][2]
이 값이 A팀 능력치가 된다.
B팀도 동일하게 계산한다.이후 백트래킹 진행 흐름은 (1,2,3)을 계산한 뒤에는
check[3] = false로 되돌아간다.그 다음 반복문이 i=4로 진행된다.
즉 다음 경우는
1, 2, 4가 된다.
그 다음은
1, 2, 5
1, 2, 6
그 다음은
1, 3, 4
1, 3, 5
...
이렇게 조합이 체계적으로 만들어진다.
시간복잡도:O(nC(n/2) * N²), 공간복잡도:O(N²)
코드
import java.util.*;
import java.io.*;
class Main {
static int n;
static int[][] arr;
static boolean [] check;
static int min = 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];
check = 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());
}
}
dfs(0,0);
System.out.println(min);
}
public static void dfs(int depth, int start){
if(depth==n/2){
calculate();
return;
}
for(int i=start;i<n;i++){
if(!check[i]){
check[i] = true;
dfs(depth+1,i+1);
check[i] = false;
}
}
}
public static void calculate(){
int startTeam = 0;
int linkTeam = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(check[i] && check[j]){
startTeam+=arr[i][j];
}else if(!check[i] && !check[j]){
linkTeam+=arr[i][j];
}
}
}
min = Math.min(min,Math.abs(startTeam-linkTeam));
}
}
참고 글
https://st-lab.tistory.com/122
백트래킹을 통해 모든 경우의 수를 탐색했다. check[i] = true 경우 현재줄을 startTeam에 추가하겠다는 의미이다.
n이 4일경우
1,2번이 스타트 팀, 3,4번이 링크 팀.
1,3번이 스타트 팀, 2,4번이 링크 팀.
1,4번이 스타트 팀, 2,3번이 링크 팀.
위 경우를 차례대로 탐색한다.
arr[i][i], arr[j][j]는 항상 0이다.
