[알고리즘 TIL] Q14889 (백트래킹)

문제

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

트러블슈팅

1. 조합 구현

이전 문제에서는 순열과 중복 순열을 백트래킹으로 구현했는데, 이번 문제는 조합을 구현해야한다. 처음에는 어떻게 구현할지를 몰라서 알아보았다.

static void combination(int start, int depth, int n, int r) {
	// 조합이 완성된 경우
	if(depth == r) {
		System.out.println(Arrays.toString(output));
		return;
	}
	
	// start 부터 n까지 반복
	for(int i = start; i < n; i++) {
		output[depth] = arr[i];	// 현재 depth를 인덱스로 사용
		combination(i + 1, depth + 1, n, r);	// i + 1, depth + 1를 전달
	}
}

처음 백트래킹으로 순열과 조합을 공부하면서 가장 헷갈렸던 점은 왜 조합에서는 i = 0이 아니라 i = start부터 반복할까?였다.

알고 보니, 이 차이는 중복을 방지하기 위한 핵심 메커니즘이였다.

이 방식 덕분에, 예를 들어 1로 시작한 조합은 2, 3, 4...만 선택하게 되고, 2로 시작한 조합은 그보다 뒤인 3, 4, 5...만 선택하게 된다. 즉, [1, 2]가 만들어졌다면, [2, 1]은 절대 다시 만들어지지 않는다.

 

2. boolean 을 이용한 배열

처음에는 조합을 활용해 팀 A를 구성한 뒤, 남은 인원을 따로 모아 팀 B를 만드는 방식으로 접근했다. 예를 들어, 팀 A에 1, 3이 있다면, 나머지 인원 중 0, 2 등을 반복문을 통해 팀 B에 추가했다.

하지만 이 문제의 특성상, 전체 인원을 정확히 두 팀으로만 나누면 되기 때문에 팀 B를 굳이 따로 만들 필요가 없다.
→ 즉, 팀 A만 정하면 팀 B는 자동으로 정해지는 구조다.

// 조합: N명 중 N/2명을 팀 A로 선택
    private static void combination(int depth, int start) {
        if (depth == N / 2) {
            calculateDifference();
            return;
        }

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

❓ 이게 왜 조합?
처음에는 이 방식이 왜 조합인지 헷갈렸는데, 다음의 분기 방식 특징을 보고, 조합임을 깨달았다. 

분기 방식	의미
for (int i = start; i < N; i++)	조합: 고를 후보들을 줄여가며 선택. 다음 반복문에서, start+1~N만 고려하므로. 즉, [1,2]만 선택되고 [2,1]은 선택되지 않는다.
for (int i = 0; i < N; i++)	순열: 다른 세계관에서 고른 숫자여도, 다시 선택 가능. 다음 반복문에서, 0~N을 모두 다시 고려하므로. 첫 분기에서 i=0을 false(0을 안고름)로 해도, i=1이 true(1을 고름)인 세계관에서 i=0이 true(0을 고름)일 수 있다.

전형적인 조합 코드는 한 번 고른 값은 그 이후 탐색에서 다시 안 고르기 때문에 추가적인 코드가 필요없었는데, 다음 조합 분기를 위해 선택 상태를 되돌려야 하므로, visited[i] = false가 필요하다.

구현

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[][] power;
    static boolean[] visited;
    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());
        power = new int[N][N];
        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                power[i][j] = Integer.parseInt(input[j]);
            }
        }

        combination(0, 0);
        System.out.println(min);
    }

    // 조합: N명 중 N/2명을 팀 A로 선택
    private static void combination(int depth, int start) {
        if (depth == N / 2) {
            calculateDifference();
            return;
        }

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

    // 두 팀으로 나누고 능력치 차 계산
    private static void calculateDifference() {
        int teamA = 0;
        int teamB = 0;

        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (visited[i] && visited[j]) {
                    teamA += power[i][j] + power[j][i];
                } else if (!visited[i] && !visited[j]) {
                    teamB += power[i][j] + power[j][i];
                }
            }
        }

        int diff = Math.abs(teamA - teamB);
        min = Math.min(min, diff);
    }
}