재귀 백트래킹

재귀 백트래킹은 답을 한 칸씩 채워 가다가 틀린 것이 보이면 바로 한 단계 물러나 다른 값을 넣어 보는 탐색 방법입니다. 답이 될 수 없는 후보는 끝까지 만들지 않습니다. 그래서 모든 후보를 다 만들어 보는 것보다 대개 적게 따지고도 같은 답을 찾습니다.

상세

재귀 백트래킹(recursive backtracking)은 알고리즘 설계 기법 가운데 하나입니다. 문제 하나를 푸는 특정한 절차가 아닙니다. 여러 문제에 두루 입히는 뼈대입니다. 줄여서 백트래킹이라고도 부릅니다.

이 절은 먼저 답을 한 칸씩 채워 가는 과정을 트리로 그려 봅니다. 다음으로 이 기법이 되풀이하는 세 동작과, 그것을 재귀로 짜는 이유를 봅니다. 이어서 체스판에 퀸 넷을 놓는 문제를 손으로 풀고 같은 풀이를 파이썬 코드로 봅니다. 끝으로 비용, 확인을 앞당기는 요령, 쓰는 문제, 이웃 기법과의 차이를 봅니다.

미로에서 길 찾기

미로를 걷다가 갈림길을 만나면 한쪽 길을 골라 들어갑니다. 막다른 길에 닿으면 마지막으로 지난 갈림길까지 돌아옵니다. 거기서 아직 안 가 본 길로 들어갑니다.

갈림길의 길을 다 가 봤는데도 출구가 없으면 그 앞의 갈림길로 한 번 더 돌아갑니다. 재귀 백트래킹은 이 걷기를 답 찾기에 옮긴 것입니다.

부분 해와 상태 공간 트리

답이 될 수 있는 것 하나하나를 후보라고 부릅니다. 이런 문제의 후보는 대개 작은 선택 여럿을 차례로 내려서 만들어집니다. 퀸 넷을 놓는 문제라면 「첫째 가로줄의 퀸을 어느 칸에 놓나」부터 「넷째 가로줄의 퀸을 어느 칸에 놓나」까지 선택이 넷입니다.

선택을 일부만 내린 상태를 부분 해(partial solution)라고 부릅니다. 첫째와 둘째 가로줄에만 퀸을 놓은 판이 부분 해입니다. 부분 해가 이미 규칙을 어겼으면 남은 선택을 어떻게 해도 답이 나오지 않습니다.

선택을 하나씩 내려 가는 과정은 트리로 그릴 수 있습니다. 맨 위 노드는 아무것도 안 정한 상태입니다. 한 단계 내려갈 때마다 선택이 하나 늘어납니다. 맨 아래 노드 하나가 완성된 후보 하나입니다. 이 트리를 상태 공간 트리라고 부릅니다.

완전 탐색은 이 트리의 맨 아래 노드를 전부 만들어 하나씩 확인합니다. 재귀 백트래킹은 내려가는 도중에 노드마다 규칙을 확인합니다. 규칙을 어긴 노드를 만나면 그 아래를 만들지 않습니다.

가망 없는 갈래를 만들기 전에 잘라 내는 일을 가지치기(pruning)라고 합니다. 재귀 백트래킹의 가지치기는 「이 부분 해는 이미 규칙을 어겼다」를 근거로 자릅니다.

고르기 · 확인하기 · 되돌리기

재귀 백트래킹은 세 동작을 되풀이합니다. 고르기는 다음 빈칸에 넣을 값 하나를 정하는 일입니다. 확인하기는 그 값을 넣은 부분 해가 규칙을 지키는지 보는 일입니다.

되돌리기는 방금 넣은 값을 빼서 넣기 전 상태로 돌려놓는 일입니다. 이름의 백트래킹(backtracking)이 이 동작을 가리킵니다. 왔던 길을 거슬러 되짚어 간다는 뜻입니다.

되돌리기는 두 경우에 일어납니다. 첫째, 확인에서 규칙을 어긴 것이 드러났을 때입니다. 둘째, 그 값 아래로 내려가 볼 것을 다 봤을 때입니다. 둘 다 값을 빼고 그 칸의 다음 값으로 넘어갑니다.

한 칸에 넣을 값을 다 써 봤으면 그 칸에서 할 일이 끝납니다. 그때는 앞 칸으로 돌아가 앞 칸의 값을 바꿉니다. 미로에서 갈림길의 길을 다 가 보고 그 앞 갈림길로 돌아가는 것과 같습니다.

재귀로 짜는 이유

재귀는 함수가 자기 자신을 다시 부르는 것입니다. 재귀 백트래킹에서는 함수 한 번이 빈칸 하나를 맡습니다. 그 칸에 값을 넣은 다음 자기 자신을 불러 다음 칸을 맡깁니다.

불린 함수가 끝나서 돌아오면 앞 칸을 맡은 함수로 흐름이 돌아옵니다. 이것이 「앞 칸으로 돌아간다」입니다.

함수마다 저절로 기억되는 것은 「이 칸에서 몇 번째 값까지 넣어 봤나」입니다. 그래서 짜는 사람이 그것을 따로 적어 둘 필요가 없습니다. 다만 여러 함수가 함께 쓰는 판에 넣은 값은 저절로 빠지지 않습니다. 돌아가기 전에 짜는 사람이 직접 빼서 판을 되돌려야 합니다.

함수마다 기억하는 값은 호출 스택에 쌓입니다. 호출 스택은 아직 끝나지 않은 함수 호출을 순서대로 기억해 두는 메모리 영역입니다. 함수가 끝나면 맨 위의 기억이 빠지고 바로 아래 호출이 하던 일을 이어 갑니다.

재귀가 끝나려면 더 부르지 않고 바로 돌아오는 경우가 있어야 합니다. 이런 경우를 기저 사례(base case)라고 부릅니다. 재귀 백트래킹에서는 빈칸을 다 채운 때가 기저 사례입니다. 그때 지금 판을 답으로 적고 돌아옵니다.

함수 하나가 하는 일을 그림으로 그리면 아래와 같습니다. 「다음 칸을 맡을 함수를 부름」에서 같은 그림이 한 단계 아래에서 다시 시작됩니다.

flowchart TD
    S{"빈칸을 다 채웠나"}
    W["답으로 적고 돌아감"]
    P{"이 칸에 넣어 볼 값이 남았나"}
    B["앞 칸을 맡은 함수로 돌아감"]
    C{"값을 넣어도 규칙을 지키나"}
    R["값을 넣고 다음 칸을 맡을 함수를 부름<br/>돌아오면 값을 뺌"]
    S -->|예| W
    S -->|아니오| P
    P -->|아니오| B
    P -->|예| C
    C -->|아니오| P
    C -->|예| R
    R --> P

재귀를 쓰지 않고 스택을 직접 두고 반복문으로 짤 수도 있습니다. 스택은 마지막에 넣은 것을 먼저 꺼내는 자료구조입니다.

두 방식이 하는 일은 같습니다. 재귀로 짜면 호출 스택이 그 스택 노릇을 대신해서 코드가 짧아집니다. 이름의 「재귀」는 흔히 이렇게 짠다는 데서 붙었습니다.

퀸 넷 놓기로 한 번 풀기

N-퀸 문제는 n × n 체스판에 퀸 n 개를 서로 공격하지 못하게 놓는 문제입니다. 퀸은 같은 가로줄, 같은 세로줄, 같은 대각선 위의 말을 공격합니다. 그러니 어느 두 퀸도 줄이나 대각선을 함께 쓰면 안 됩니다.

여기서는 4 × 4 판에 퀸 넷을 놓습니다. 가로줄을 행, 세로줄을 열이라고 부르겠습니다. 한 행에 퀸이 둘이면 서로 공격하므로 행마다 퀸 하나씩 놓습니다.

그러면 선택은 「0행부터 3행까지 각 행의 퀸을 몇 열에 놓나」 넷입니다. 행과 열은 뒤의 코드와 맞추려고 0 부터 셉니다.

0행의 퀸을 0열에 놓고 시작합니다. 1행에서는 0열이 같은 열, 1열이 대각선이라 2열에 놓습니다. 2행에서는 네 열이 전부 앞의 두 퀸 중 하나와 줄이나 대각선이 겹칩니다. 놓을 열이 없으므로 1행으로 돌아갑니다.

1행의 퀸을 3열로 옮깁니다. 2행은 1열에 놓입니다. 3행에서 또 네 열이 다 막힙니다. 2행으로 돌아가 남은 열을 봐도 놓을 곳이 없습니다. 1행에도 남은 열이 없습니다. 0행까지 돌아갑니다.

0행의 퀸을 1열로 옮깁니다. 이번에는 1행 3열, 2행 0열, 3행 2열에 차례로 놓입니다. 퀸 넷이 다 놓였으므로 답입니다. 행 순서대로 열을 적으면 [1, 3, 0, 2] 입니다.

이 과정을 트리로 그리면 아래와 같습니다. 「막힘」이 붙은 노드에서 아래로 내려가지 못하고 위로 돌아갔습니다.

flowchart TD
    R["아무것도 안 놓음"]
    R --> A["0행 0열"]
    R --> E["0행 1열"]
    A --> B["1행 2열"]
    A --> C["1행 3열"]
    B --> BX["2행 · 네 열 다 막힘"]
    C --> D["2행 1열"]
    D --> DX["3행 · 네 열 다 막힘"]
    E --> F["1행 3열"]
    F --> G["2행 0열"]
    G --> H["3행 2열 · 답"]

퀸을 행마다 아무 열에나 놓는 후보는 4 × 4 × 4 × 4 = 256 가지입니다. 완전 탐색이라면 이 256 판을 다 만들어 하나씩 확인합니다. 재귀 백트래킹은 퀸 여덟 번을 놓아 보고 첫 답에 닿았습니다. 0행 0열 아래로 달린 후보 64 판은 끝까지 하나도 만들지 않았습니다.

같은 풀이를 코드로

앞의 손풀이를 파이썬으로 옮기면 아래와 같습니다. 이번에는 첫 답에서 멈추지 않고 답을 전부 모읍니다.

def solve(n):
    cols = []    # cols[r] = r행 퀸의 열
    found = []

    def safe(c):
        r = len(cols)
        for pr, pc in enumerate(cols):
            if pc == c:
                return False
            if abs(pc - c) == r - pr:
                return False
        return True

    def place():
        if len(cols) == n:
            found.append(cols[:])
            return
        for c in range(n):
            if safe(c):
                cols.append(c)  # 고르기
                place()
                cols.pop()      # 되돌리기

    place()
    return found

solve(4)       # [[1,3,0,2], [2,0,3,1]]
len(solve(8))  # 92

cols 는 지금까지 놓은 퀸의 열을 행 순서대로 담는 목록입니다. 이 목록이 부분 해입니다. 목록의 길이는 다음에 채울 행 번호입니다.

safe 가 확인하기입니다. 새 퀸을 c 열에 놓았을 때 앞의 퀸과 열이 같은지 봅니다. 대각선은 두 퀸의 행 차이와 열 차이가 같은지로 봅니다. 하나라도 걸리면 False 를 돌려줍니다.

place 가 빈칸 하나를 맡는 재귀 함수입니다. 첫 if 가 기저 사례입니다. 행을 다 채웠으면 지금 판을 복사해 found 에 넣고 돌아갑니다. cols 는 뒤에서 pop 으로 계속 바뀝니다. 복사하지 않고 그대로 넣으면 끝에 가서 빈 목록만 남습니다.

반복문은 이 행의 열을 하나씩 고릅니다. safe 를 지나면 cols.append(c) 로 퀸을 놓고 place() 로 다음 행을 맡깁니다. 그 호출이 돌아오면 cols.pop() 으로 퀸을 뺍니다. 이 한 줄이 되돌리기입니다.

cols.pop() 을 빼먹으면 다음 열을 시험할 때 방금 놓은 퀸이 판에 남아 있습니다. 그러면 남은 행을 확인할 때 엉뚱한 퀸과 견주게 되어 답이 틀어집니다. 재귀 백트래킹을 처음 짤 때 자주 나는 실수가 이 되돌리기를 빠뜨리는 것입니다.

4 × 4 판의 답은 둘입니다. 둘째 답 [2, 0, 3, 1] 은 첫 답을 좌우로 뒤집은 판입니다. 8 × 8 판에는 답이 92 개 있습니다.

비용

가장 운이 나쁠 때 재귀 백트래킹은 완전 탐색보다 나아지지 않습니다. 규칙 위반이 맨 마지막 칸에서야 드러나면 트리의 노드를 거의 다 만들게 됩니다. 칸이 n 개이고 칸마다 넣을 값이 k 개면 맨 아래 노드가 kⁿ 개입니다. 빅오 표기법으로 O(kⁿ) 입니다.

kⁿ 은 칸이 하나 늘 때마다 k 배가 되는 수입니다. 이렇게 입력이 조금 커져도 후보 수가 폭발하듯 늘어나는 현상을 조합 폭발이라고 부릅니다. 8 × 8 퀸 문제만 해도 행마다 아무 열에나 놓는 후보가 8⁸, 약 1,677만 가지입니다.

보통 얼마나 덜 따지는지는 문제와 규칙에 달려 있습니다. 위반이 앞 칸에서 일찍 드러날수록 큰 갈래를 일찍 잘라 냅니다. 미리 셀 수 있는 공식은 없어서 입력마다 돌려 봐야 압니다.

메모리는 적게 듭니다. 들고 있는 것은 지금 내려와 있는 갈래 하나뿐이라 트리 깊이, 곧 칸 수만큼만 씁니다. 다만 재귀가 너무 깊어지면 호출 스택이 바닥나 프로그램이 멈춥니다. 이것을 스택 오버플로라고 부릅니다.

확인을 앞당기는 요령

재귀 백트래킹을 빠르게 만드는 방법은 대개 하나로 모입니다. 틀린 후보를 더 일찍 알아내거나 아예 안 만드는 것입니다.

첫째는 규칙 일부를 선택의 모양에 넣어, 그 규칙을 어기는 후보가 아예 안 생기게 하는 것입니다. 퀸 문제의 「행마다 하나」가 그 예입니다. 행마다 열 하나를 고르게 짰으니 같은 행에 둘을 놓는 후보는 애초에 만들어지지 않습니다. 그 규칙은 확인할 필요조차 없어집니다.

둘째는 남은 칸에 넣을 수 있는 값을 미리 줄여 두는 것입니다. 값을 하나 넣을 때마다 그 값 때문에 다른 칸에서 못 쓰게 된 값을 지웁니다. 어떤 칸에 쓸 값이 하나도 안 남으면 그 칸까지 내려가기 전에 되돌아갑니다. 이 방법을 전방 검사(forward checking)라고 부릅니다.

셋째는 고를 칸의 순서를 바꾸는 것입니다. 넣을 수 있는 값이 가장 적게 남은 칸부터 채우면 막다른 길이 일찍 드러납니다. 스도쿠를 손으로 풀 때 후보 숫자가 하나뿐인 칸부터 채우는 것과 같은 생각입니다.

이 기법으로 푸는 문제

재귀 백트래킹은 정해진 규칙을 모두 지키는 조합을 찾는 문제에 씁니다. 변수 여럿에 값을 하나씩 정하되 변수끼리 지켜야 할 규칙이 있는 문제를 제약 충족 문제라고 합니다. 이런 문제를 정답이 보장되게 풀 때 가장 먼저 꺼내는 풀이입니다.

규칙을 지키는 답을 전부 나열하는 일에도 씁니다. 원소 n 개로 만드는 순열이나 조합을 빠짐없이 뽑을 때 이 뼈대를 그대로 씁니다.

정규 표현식을 처리하는 엔진 가운데에도 이 방식으로 문자열을 맞춰 보는 것이 많습니다. 패턴 (a|ab)c 를 문자열 abc 에 맞춘다고 해 봅시다. 엔진은 먼저 a 갈래를 골라 a 를 맞춥니다. 다음 글자 b 가 c 와 안 맞으면 되돌아가 ab 갈래로 다시 맞추고, 남은 c 까지 맞춰 성공합니다.

이 되돌아가기는 패턴에 따라 횟수가 지수로 불어납니다. 반복 기호가 겹친 (a+)+b 에 b 없이 a 만 길게 늘어선 문자열을 넣으면, 엔진은 그 a 들을 반복마다 나누는 방법을 하나하나 다 시험한 뒤에야 실패를 알립니다. 그동안 응답이 멈춥니다. 이 약점을 노려 서버를 멈추게 하는 공격을 ReDoS(Regular expression Denial of Service, 정규 표현식 서비스 거부)라고 부릅니다.

이웃 기법과의 차이

재귀 백트래킹은 완전 탐색에서 출발해 후보를 덜 보는 기법 가운데 하나입니다. 이웃 기법들과는 무엇을 근거로 버리거나 줄이느냐가 다릅니다.

아래 표의 마지막 칸에 나오는 최적해는 규칙을 지키는 답 가운데 어떤 값을 가장 크게 또는 가장 작게 만드는 답입니다. 가방에 담은 물건의 값 합이 가장 큰 담기가 그렇습니다. 이런 최적해를 찾는 문제를 최적화 문제라고 부릅니다.

표에 나오는 부분 문제는 원래 문제에서 일부를 떼어 낸 더 작은 문제입니다. 부분 해와 이름이 비슷하지만 가리키는 것이 다릅니다. 부분 해는 이미 내린 선택입니다. 부분 문제는 그 선택 뒤에 남은, 풀어야 할 일입니다.

재귀 백트래킹은 답을 전부 모은 뒤 견주면 최적해를 낼 수 있습니다. 하지만 「더 좋아질 가망이 없다」로는 자르지 못합니다. 그 판단까지 더한 것이 분기 한정입니다.

동적 계획법과는 겹치는 계산을 다루는 방식이 다릅니다. 재귀 백트래킹은 서로 다른 갈래에서 똑같은 부분 문제를 만나도 매번 다시 풉니다.

부분집합 합 문제로 보면 이렇습니다. 원소 1, 2, 3 을 차례로 넣거나 뺄 때, 「1 과 2 를 넣고 3 을 뺀」 갈래와 「1 과 2 를 빼고 3 을 넣은」 갈래는 둘 다 합이 3 입니다. 두 갈래에 남은 일은 「남은 원소로 목표에서 3 을 뺀 값을 만들 수 있나」로 똑같습니다. 재귀 백트래킹은 이 부분 문제를 두 번 풉니다.

동적 계획법은 부분 문제의 답을 적어 두고 다시 써서, 같은 부분 문제를 한 번만 풉니다. 이처럼 따지는 양이 덜 불어나는 풀이가 알려진 문제라면 그쪽을 씁니다.

트리를 훑는 순서로 보면 재귀 백트래킹은 깊이 우선 탐색입니다. 깊이 우선 탐색은 한 갈래를 끝까지 내려간 뒤에 돌아와 옆 갈래로 가는 순서입니다. 재귀 백트래킹은 이 순서로 상태 공간 트리를 훑으면서 가지치기를 얹은 것입니다.

관련 항목

재귀 백트래킹과 나란히 쓰는 설계 기법

완전 탐색 · 분기 한정 · 동적 계획법 · 그리디 알고리즘 · 분할 정복 · 메모이제이션 · 알고리즘 설계 기법

재귀 백트래킹을 이루는 부품

상태 공간 트리 · 부분 해 · 가지치기 · 재귀 · 기저 사례 · 호출 스택

재귀 백트래킹이 트리를 훑는 순서

깊이 우선 탐색 · 너비 우선 탐색 · 스택 (자료구조) · 반복적 깊이 증가 탐색

재귀 백트래킹으로 푸는 문제

N-퀸 문제 · 스도쿠 · 부분집합 합 문제 · 그래프 색칠 문제 · 제약 충족 문제 · 해밀턴 경로 · 순열 · 조합 · 미로 탐색

재귀 백트래킹의 가지치기를 앞당기는 요령

전방 검사 · 제약 전파 · 최소 잔여 값 휴리스틱 · 아크 일관성 · DPLL 알고리즘

재귀 백트래킹으로 문자열을 맞추는 도구와 그 위험

정규 표현식 · 정규 표현식 엔진 · ReDoS · 파국적 백트래킹

재귀 백트래킹의 비용을 재는 도구

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 조합 폭발 · 스택 오버플로

재귀 백트래킹이 속하는 상위 분류

알고리즘 · 탐색 알고리즘 · 최적화 문제 · 최적해