백트래킹이란? - 백트래킹으로 조합 구현하기 [Java/자바]

백트래킹이란?

백트래킹이란 해를 찾는 도중에 주어진 조건에 부합하지 않는 상태일 때, 즉시 이전 상태로 되돌아가 다른 경우의 수를 탐색하는 방법을 말합니다.

 

보통 이 알고리즘은 DFS나 BFS에서 사용됩니다. 모든 노드를 방문하는 알고리즘 중 하나인 DFS와 BFS에서 조건을 만족하지 않는 노드를 방문했을 때, 해당 노드로부터 연결된 모든 자식 노드들을 방문하지 않고 건너뛰는 방식입니다. 이를 가지치기(Pruning)이라고도 합니다.

 

---

 

저는 이 백트래킹을 조합의 경우의 수를 구하는 과정에서 처음 접했습니다. 따라서 m과 n이 주어졌을 때, 가능한 모든 경우의 수를 출력하는 코드를 소개하면서 백트래킹에 대해 코드와 함께 다뤄보겠습니다.

 

아래의 코드는 1부터 m까지의 정수가 있다고 했을 때, mCn의 모든 경우의 수를 나열하는 코드입니다. 코드에 대한 자세한 과정은 코드 하단에 첨부합니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        boolean[] visited = new boolean[m];
        int[] arr = new int[m];
        for(int i=1; i<=m; i++) arr[i-1] = i; // 1부터 m까지를 갖는 배열 생성

        backTracking(arr, visited, 0, m, n); // mCn의 가지수를 출력하는 함수
    }

    static void backTracking(int[] arr, boolean[] visited, int start, int m, int n) {
        if(n == 0) { // 재귀함수인 backTracking의 중단조건
            print(arr, visited, m);
            return;
        }

        for(int i = start; i < m; i++) {
            visited[i] = true;
            backTracking(arr, visited, i + 1, m, n - 1);
            visited[i] = false;
        }
    }
    static void print(int[] arr, boolean[] visited, int m) { // 가지수를 출력하기 위한 함수
        for (int i = 0; i < m; i++) {
            if(visited[i]) System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

 

이 코드의 입력을 아래와 같이 주어졌다고 해봅시다.

4 2

 

그러면 아래와 같은 출력 결과를 가져옵니다.

1 2 
1 3 
1 4 
2 3 
2 4 
3 4

 

그럼 이제 이 코드에 대한 과정을 그림과 함께 살펴보겠습니다.

 

예제와 같은 경우의 입력이 주어졌다고 하면, main 메서드에서 초기에 backTracking(arr, visited, 0, 4, 2)를 호출하게 됩니다.

 

이제 backTracking(arr, visited, 0, 4, 2) 내의 반복문에 진입하여 backTracking(arr, visited, 1, 4, 3)을 호출합니다.

이와같은 과정은 backTracking의 마지막 인자인 n이 0이 될 때까지 반복합니다. 아래는 해당 과정까지를 나타냅니다.

 

이후, print 메서드에서 visited == true인 것만 출력하게 됩니다. 보시면, 1과 2가 출력됨을 알 수 있습니다.

 

이후, 과정 또한 아래와 같이 진행됩니다.

 

 

이러한 과정이 진행됨으로써 우리가 원하는 결과를 얻을 수 있습니다.

 

이상으로 백트래킹에 대한 개념과 적용 코드에 대해서 알아봤습니다.