[알고리즘] 백트래킹 완전정복을 향해🤸‍♀️

참고로 풀어볼 만한 문제 모음

• [백준14888] 연산자 ✔
• [백준 9663]
• [백준 14501]
• 백준 [1799] : 비숍

백트래킹

백트래킹이란 여러가지 조합의 경우의 수를 재귀함수로 탐색해가며 찾아내는 알고리즘이다.
백트래킹 구현의 핵심은 for문의 범위와 내부 함수를 잘짜는 것이며 그를 위해서는 다음 재귀에서 어디부터 어디까지 탐색해야 하는가를 잘 따져보는 것이 중요하다. 현재 시점에서 다음 재귀를 불러올 때 다음 재귀의 탐색 범위를 잘 따져보면 for문의 범위를 상황에 적절하게 잘 구현할 수 있다.

백트래킹의 기본 format

// 백트래킹 사용
// 사용 예시 : combination(arr, visited, 0, n, r)
static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
    if(r == 0) {
        print(arr, visited, n);
        return;
    } 

    for(int i=start; i<n; i++) {
       //visited[i] = true; 혹은 뭔가 수행하고 싶은 조합 기준의 뽑기 기능
        combination(arr, visited, i + 1, n, r - 1);
        //visited[i] = false; 뽑은거 원상태로 돌리기 
    }
}

다음과 같이 원하는 갯수 만큼의 수를 조합에서 뽑아냈으면 재귀함수 가장 상단에서 if(r ==0)처럼 카운트를 세서 처리한다.
이때 조합을 뽑은 뒤 처리할 일을 처리한 뒤 return 해주면 된다.

for문에서의 기본 형식은 start부터 전체 개수를 돌고 start는 재귀가 호출될 때마다 i+1로 증가하는 것이다.

백트래킹의 기본 및 다양한 형식

1. 기본 형식

static void combination(int[] arr, int start, int n, int r) {
    if(r == 0) {
        // 조합을 다 뽑으면 수행할 내용 
        return;
    } 

    for(int i=start; i<n; i++) {
       //수행하고 싶은 조합 기준의 뽑기 기능
        combination(arr, i + 1, n, r - 1);
        //뽑은거 원상태로 돌리기 
    }
}

위에서 보았던 것과 중복이지만 이와 같은 형식이 가장 기본 형식이다.
시작 지점으로부터 배열의 끝까지 탐색을 하는 것을 기본으로 하며
배열에서 마주친 숫자를 조합에서 뽑을 수 있는 경우 뽑고 두번째(혹은 다음 n번째) 숫자를 뽑기 위해 현 위치의 바로 다음 지점을 다음 재귀의 시작지점으로 설정하고 다시 탐색하도록 한다.
이 때 뽑아야 할 갯수는 하나 줄어드므로 r-1도 재귀의 입력수로 넣어준다

이 때 중요한 것은 이 방법을 쓰는 경우 굳이 boolean visit와 같은 것을 사용해서 숫자를 이미 뽑았는지, 방문했는지 여부를 파악할 필요가 없다는 것이다.
왜냐하면 그림에서 보는 바와 같이 우리가 재귀 탐색을 현 위치의 바로 다음부터 재귀함수가 탐색 하도록 설정하였기 때문에 재귀는 절대 중복으로 탐색할 수 없게 된다.

2. 여러 개의 옵션 중 하나씩을 택해서 조합을 만드는 형식

이 형식은 [백준14888]연산자 문제에서 활용되고 있다.
여러 개의 옵션 중 하나씩을 택해서 조합을 만드는 형식은 말 그대로 제한된 갯수가 있는 여러 집단들의 옵션에서 하나씩 뽑아 조합을 만들어내는 방법이다.

아래의 코드는 숫자 사이에 들어올 수 있는 연산자 (덧셈, 뺄셈, 곱셈, 나눗셈) 4가지가 각각 뽑을 수 있는 횟수가 정해져있을 때 활용할 수 있는 코드이다.
이와 같이 뽑으려는 집단이 여러개이고 그것의 갯수가 한정적일 때 활용할 수 있다.

 public static void combination(int num, int index) {
        if (index == n) {
            max = Math.max(num, max);
            min = Math.min(num, min);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if(psmd[i]>0){
                psmd[i] --;
                switch (i){
                    case 0: combination(num+numbers[index],index+1); break;
                    case 1: combination(num-numbers[index],index+1); break;
                    case 2: combination(num*numbers[index],index+1); break;
                    case 3: combination(num/numbers[index],index+1); break;
                }
                psmd[i] ++;
            }
        }

이 때의 핵심은 for문에서 start를 매번 다르게 주는 것이 아니라 그냥 처음부터 끝 인덱스를 계속 탐색하는것이다.
이렇게 하는 이유는 시작 지점에서의 옵션의 갯수를 모두 소진하였을 때 다음 재귀에서 시작 지점의 옵션보다 앞에 있는 옵션도 탐색할 수 있어야 하기 때문이다.

결과 조합 building 과정

백트래킹의 조합 결과는 백트래킹 input 내에 변수를 주어서 build 할 수 있다.
단순히 글로벌한 숫자로 다른 쪽에도 값을 알려주어야 하는 것이 아니라 if( r ==0) 함수 부분에서만 처리해도 되는 백트래킹 조합 결과인 경우에는 그냥 백트래킹 재귀함수 인풋 변수로 정의하는 것이 깔끔하다
이렇게 함수 인풋값으로 결과 조합을 building 하는 경우 그냥 재귀함수를 호출할 때마다 해당 인풋값으로 값을 build한 값을 넣어주면 된다.

combination(result+numbers[index],index+1);
combination(resultString+string[index],index+1);

이런식으로 재귀함수의 입력값에 직접 build 할 수 있다!
당연히 단순 변수는 재귀함수 내부에서 직접 +로 붙여주어야 하며
재귀가 return 됨에 따라 해당 값도 다시 원상복구 되니까 값을 수동으로 되돌릴 필요가 없다

백트래킹 주의사항

index로 탐색 시 list 형식은 사용 경계하기

백준 1759 암호만들기 문제처럼 백트래킹을 이용하고 싶은데 탐색하는 배열 원소들이 외부에서 넣었다가 빠졌다가 하면서 유동적으로 변하는 경우
뭔가 ArrayList나 Queue 같은 형식으로 dfs 전후에 remove와 add를 넣고 싶은 욕구가 생긴다.

그러나!!!!!! 절대로 그러면 안된다.
왜냐하면 for문으로 탐색할 때 해당 index가 그대로 고정되는 것이 아니라 유동적으로 넣고 빠지면서 index가 하나씩 앞으로 당겨지기 때문이다
예를 들어

for(int i = start; i<arrayList.size();i++){
	
    arrayList.remove(i);
    dfs(i+1,n);
    arrayList.add(i);
}

이런 식의 코드는 arrayList의 처음 index의 원소가 빠지고 재귀함수 호출 후 add될 때 가장 마지막 index의 원소로 다시 들어가고, 다음 원소는 처음 index의 원소가 되기 때문에
다음 탐색 시 탐색해야하는 다음 원소는 처음 index의 원소가 되어서 탐색이 안되고 그 다다음 원소부터 탐색하게 되는 불상사가 생긴다.

위의 코드는 단순해서 그냥 배열로 만들면 되지만 앞에서 언급했다시피 재귀 외부에서도 원소가 유동적으로 넣었다 빠졌다 하는 구조의 배열을 백트래킹으로 다음과 같이 탐색하고 싶을 때는 어떻게 해야할까?

대안책

위 코드는 다음과 같이 바꿀 수 있다.

static boolean[] visited = new boolean[arrayList.size()];

for(int i = start; i<arrayList.size();i++){
	
    visit[i] = true;
    dfs(i+1, n);
    visit[i] = false;
    
}

//외부에서 해당 ArrayList의 원소를 뺄 때
visit[i] = true;
//외부에서 해당 ArrayList의 원소를 넣을 때
visit[i] = false;

이렇게 단순하게 해결이 가능하다!
그러니 꼭 백트래킹에서 탐색해야 할 배열의 원소를 외부에서 넣었다 뺐다 할 때에는 boolean 형식의 배열 visit를 활용하자

단순 처음부터 끝까지의 탐색이 필요한 경우

백준 1799 비숍 문제를 참고하여 이해하면 좋다.

우리가 익숙한 백트래킹은 조합을 찾는 경우처럼 반드시 몇개를 뽑았는지 count해서 목표치만큼 뽑았으면 if문을 걸어 return을 해주었다
그러나 뚜렷한 목표치가 없이 처음부터 끝까지 탐색을 해야하는 경우에도 백트래킹을 쓴다.
백트래킹은 단순 조합에서만 쓰이는 것이 아니라 여러 가지 뽑았다 빼보는(넣었다 빼보는) 경우의 수를 따지는 것이다
이런 경우에는 재귀함수 return을 언제 해야하는지 난감해진다.

백트래킹의 기본 프레임에 너무 매몰되다보니 한 가지 간과한 사실이 있다.
정말 기본적인 얘기지만 모든 함수는 함수가 끝나면 return 된다는 것이다 (void 함수같이 return 값이 없는 경우)
따라서 단순하게 처음부터 끝까지의 탐색이 필요한 경우
if문으로 따로 return 할 시점을 찾는 대신 그냥 for문으로 탐색만 하면 된다
왜냐하면 이 함수에서는 전체 탐색이 완료했을 시점이 백트래킹 탐색의 조건을 충족하여 return 할 시점이기 때문이다!

그러면 이제 return 전에 조건이 충족하면 처리했던 기능은 어떻게 되냐가 문제이다.
이것은 단순히 재귀함수의 return(끝) 직전에 그 기능을 지속적으로 업데이트 해주면서 원하는 결과값을 가져오면 된다.

    static void dfs(int index, boolean black, int cnt) {

        for (int i = index; i < N * N; i++) {
            int x = i / N;
            int y = i % N;

            if (board[x][y] == 0 || isBlack[x][y] != black || !check(x, y))
                continue;

            visited[x][y] = true;
            dfs(i + 1, black, cnt + 1);
            visited[x][y] = false;
        }

        res[black ? 0 : 1] = Math.max(res[black ? 0 : 1], cnt);
    }

빠른 이해를 위해 예시 백트래킹 코드를 가져왔다.
이 문제는 체스 판 전체에서 비숍이라는 말이 올라갈 수 있는 경우의 최대 갯수를 구하는 문제였는데
따라서 갯수가 정해진 조합을 뽑는 경우가 아니라 처음부터 끝까지 체스판 탐색을 통해 말이 올라갈 수 있는지 판단하고 올렸다 빼가면서 최대 갯수의 경우를 찾아야 했다.

코드를 보면 단순히 for문으로 모든 체스판의 칸을 탐색하고 있으며 체스판에 말을 놓을 수 있는 조건이 되면 visit를 통해 말을 놓고 재귀를 돌리는 형식으로 되어있다.
if문을 통해 return을 하는 조건은 주어져있지 않고 대신에 함수가 return되는 시점인 함수의 마지막 부분마다 말의 개수를 나타내는 파라미터인 count의 최대값을 지속적으로 업데이트 하고있다.