[알고리즘] 백트래킹 - 재귀를 통한 구현과 응용 문제

백트래킹을 공부하기 전에 BFS와 재귀를 꼭 꼭 먼저 공부하는 것을 추천합니다. 구현의 상당 부분이 재귀로 이루어지고 BFS와 비슷한 이론의 느낌이 나기 때문입니다.

[알고리즘] BFS와 DFS

[알고리즘] 재귀 - 귀납적 사고와 재귀 함수 구조 짜기

바킹독님의 실전 알고리즘 강의를 듣고 이해한 것을 바탕으로 정리한 글입니다. 글을 보고 베끼진 않았으며 제가 이해한 부분을 토대로 작성했습니다.

[실전 알고리즘] 0x0C강 - 백트래킹

---

백트래킹이란 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. 예를 들면 역전재판 게임이나 여느 비슷한 선택지가 존재하는 JRPG 게임들은 백트래킹과 굉장히 유사한 방식으로 플레이된다. 이런 게임들은 아래처럼 작동된다.

 

선택지 1. -> 선택지 1-1. -> Game Over

                -> 선택지 1-2. -> 통과

선택지 2. -> Game Over

 

이런 선택지에서 2. 선택했다가 게임 오버니까 다시 돌아와서 1을 선택하고... 즉 현재 상태에서 가능한 모든 선택지를 방문하는 알고리즘이다. 현재 상태로 돌아와서 다시 선택하는 느낌으로 구현을 하다 보니 거의 모든 구현이 재귀적으로 이루어진다. 

 

백트래킹을 공부하면서 알아둬야할 포인트가 세 개 정도 있다.

1. 상당히 구현이 힘들다. 풀이를 떠올려도 코드로 옮기기 어렵다.

2. 실수하기 쉽고 실수한 부분을 찾기 어렵다.

3. BFS처럼 기본 형태를 확실히 익혀두고 응용하는 식으로 학습하는 편이 좋다.

---

바로 문제로 들어가서 구현해볼건데, N과 M 1번 시리즈이다.

 

15649번: N과 M (1)

문제는 1 ~ N 까지의 자연수 중 중복이 없게 M개만큼 선택해서 출력하면 된다. 이제 막 백트래킹 이론을 배우고 구현하려 하면 어찌어찌 재귀로 구현할 수 있을 것이다. 하지만 이 문제가 백트래킹의 가장 대표적이고 전형적인 문제이고 이 문제를 통해 기본 형태를 익혀보자.

 

구현을 들어가기 전에 재귀처럼 미리 base condition과 재귀식만 생각해 보자.

기본 알고리즘은 빈 리스트에서 수를 하나씩 추가하면서 길이가 M이면 출력하는 방식이다.

위의 방식처럼 상태 공간 트리를 만들면서 진행하는데, 상태 공간 트리라는 용어는 몰라도 된다.

 

k개까지 리스트를 채웠다고 가정하면 k + 1 번째는 사용하지 않은 문자를 추가하면 된다. 이를 바탕으로 구현해 보자. 다시 말하지만 가장 기본적인 백트래킹의 형태이므로 BFS 기본 형태를 외우다시피 익혔듯이 이도 마찬가지로 익히자.

/** 탐색 BackTracking **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define MAX 502
using namespace std;

int n, m; // 1 ~ n 까지 자연수 중 m 개를 선택한다.
int res[MAX];
bool visited[MAX];

void func(int k)
{
    // 현재 k개까지 수를 선택함
    if (k == m)
    {
        // base condition
        for (int i = 0; i < m; i++)
            cout << res[i] << ' ';
        cout << '\n';
        return;
    }

    for (int i = 1; i <= n; i++)
    {
        if (!visited[i])
        {
            // 숫자 i가 사용되지 않았으면
            res[k] = i;
            visited[i] = true;
            func(k + 1);
            visited[i] = false; // k번째 수를 i로 정한 모든 경우를 출력했으니 다시 i를 사용해도 됨.
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    func(0);
}

이 코드에서 어려운 부분이 아마 재귀식 부분일 것이다.

for (int i = 1; i <= n; i++)
{
    if (!visited[i])
    {
        // 숫자 i가 사용되지 않았으면
        res[k] = i;
        visited[i] = true;
        func(k + 1);
        visited[i] = false; // k번째 수를 i로 정한 모든 경우를 출력했으니 다시 i를 사용해도 됨.
    }
}

이해가 잘 가지 않는다면 절차식으로 이해하기보다 귀납적으로 이해해 보면서 다시 재귀 부분을 공부해 보자.

 

백트래킹은 가지치기 때문에 시간 복잡도 계산이 굉장히 힘들다. 따라서 N이 많이 작으면 백트래킹으로 구현 후 가장 최악의 경우를 직접 돌려보자.

---

이제 이 기본틀이 익숙해졌으면 아래의 문제들도 꼭 꼭 풀어보자. 

[BOJ] C++ 9633 N-Queen - 백트래킹 구현하기

 

[BOJ] C++ 1182 부분수열의 합 - 백트래킹 구현하기