[Algorithm]백트래킹 - 2. 연습(부분 집합의 합)

jhooooon 2025. 5. 6. 01:58

그래프의 탐색 알고리즘(DFS, BFS, 다익스트라 등)은 틀(공식)이 어느 정도 정해져 있기 때문에 대부분 비슷한 방식으로 문제를 해결하지만 백트레킹은 이렇다할 틀이 없고 문제를 푸는 사람마다 다르게 만들 수 있다. 따라서 많은 연습을 통해 문제를 해결하는 요령을 익혀야 한다.

부분 집합 합 문제

부분 집합이란 어떤 수들이 주어 졌을 때 이 수들을 조합 할 수 있는 경우의 수 이다.
{1, 2, 3} 이 주어 진다면 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}이 {1, 2, 3}의 부분 집합이다.
각 수를 사용하지 않는 경우, 사용하는 경우를 깊이 우선 탐색으로 뿌리를 내리며 탐색 하면 모든 부분 집합을 찾아 낼 수 있다. 이 방법으로 부분 집합을 찾는 다면 트리 모양이 된다.

부분 집합 합 문제는 어떤 수들이 주어 졌을 때 부분 집합의 합이 K가 되는 부분 집합을 찾는 문제 이다.
부분 집합의 합이 K가 되는 것만 찾으면 되기 때문에 깊이 우선 탐색 도중 해가 될 수 없는 경우 백트래킹 해준다면 비용을 절약할 수 있다.

import java.util.*;

class Solution {

    public void solution(int n, int k) {
        ArrayList<int[]> result = new ArrayList<>(); // 결과를 담을 List

        Stack<Node> stack = new Stack<>(); // 깊이 우선 탐색에 사용 될 Stack
        int[] start = new int[n]; // 숫자 조합을 담을 배열
        stack.push(new Node(0, start, 0)); // 깊이 우선 탐색 시작노드

        int cnt = 0; // while문이 몇번 실행되는지 확인하기 위한 변수
        while(!stack.isEmpty()) { // stack이 비워질때 까지 반복
            cnt++; // while문이 한번 돌때마다 cnt + 1
            Node current = stack.pop(); // 현재 노드를 꺼냄.

            if(current.num == n) { // 현재 번호가 마지막 번호 이면
                if(current.sum == k) { // 현재 노드의 sum 값과 k 값을 비교 하고 같으면
                    result.add(current.result); // 조합을 결과 List에 담음.
                }
                continue; // 마지막 번호 이므로 다음 Node 꺼내러 GO
            }

            if(backtrack(current, k)) { // 유망 함수
                continue; // 유망 함수가 true면 백트래킹.
            }

            int[] includeResult = current.result.clone(); // 현재까지 결과를 복사 하고
            includeResult[current.num] = current.num + 1; // 현재 자리에 현재 숫자 추가
            // Node(현재 숫자, 현재까지 조합 된 숫자 배열, 현재까지 조합한 번호의 합)
            Node include = new Node(current.num + 1, includeResult, current.sum + includeResult[current.num]);
            stack.push(include); // Stack에 현재 숫자를 사용하는 Node 삽입

            int[] excludeResult = current.result.clone(); // 현재까지 결과를 복사
            // Node(현재 숫자, 현재까지 조합 된 숫자 배열, 현재까지 조합한 번호의 합)
            Node exclude = new Node(current.num + 1, excludeResult, current.sum);
            stack.push(exclude); // Stack에 현재 숫자를 사용하지 않는 Node 삽입

        }

        // 결과 출력
        for(int[] r : result) {
            System.out.print("{ ");
            for(int num : r) {
                System.out.print(num == 0 ? "" : num + " ");
            }
            System.out.println("}");
        }
        System.out.println(cnt + "번 반복");
    }

    boolean backtrack(Node node, int k) { // 유망 함수
        return k < node.sum; // 현재까지 조합의 합이 이미 k를 넘겼으므로 더 진행할 필요 없음.
    }

    class Node {
        int[] result; // 조합 된 숫자 배열
        int num; // 탐색 숫자
        int sum = 0; // 탐색 된 조합의 합

        Node(int num, int[] result, int sum) {
            this.result = result;
            this.num = num;
            this.sum = sum;
        }

    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(3, 2);
    }

}

해당 소스를 실행하면 13번 만에 조합을 찾아낸다. 여기서 백트래킹 하는 부분을 빼고 실행시키면 15번 만에 조합을 찾아 내는 것을 볼 수있다. 얼마 차이가 나지 않는것 같지만 n, k를 12, 21로 설정 한다면 백트래킹을 했을 때 2523번, 백트래킹을 제외 했을 때 8191번 으로 많은 차이가 난다.
해당 소스에서는 백트래킹 조건이 하나밖에 없지만 여러 조건을 더 추가해 while문의 횟수를 더 줄일 수도 있다. 예를 들면 조합이 k가 되는 수를 찾았을 때 더 진행하지 않고 백트래킹하는 로직을 유망 함수에 추가할 수 있다. 이처럼 백트래킹은 문제마다 다양한 유망 함수가 만들어 질 수 있다.