재귀와 귀납 - 작은 문제로 큰 문제 풀기

이 장에서 배우는 것

앞 장에서 모든 경우를 빠짐없이 살펴보는 방법을 익혔다. 경우의 수가 여러 단계의 선택으로 만들어진다면, 반복문을 몇 겹 써야 할지 먼저 고민하게 된다. 선택 단계가 입력에 따라 달라질 때는 같은 일을 더 작은 범위에 맡기는 방식이 편리하다. 이것이 재귀(recursion)다.

재귀는 함수가 자신을 호출한다는 문법만으로 이해하기 어렵다. 현재 호출이 무엇을 책임지는지, 다음 호출에 무엇을 맡기는지, 어디에서 멈추는지를 함께 정해야 한다. 이 장에서는 남은 상자의 물품 수를 더하는 문제와 점검대 배치 문제를 통해 그 관계를 살펴본다. 마지막에는 놓을 수 없는 칸이 있는 N-퀸 변형 문제를 풀고, 탐색 함수가 실제로 몇 번 호출되는지도 출력한다.

• 작은 문제의 답을 이용해 큰 문제의 답을 설명하고, 이를 재귀 함수로 옮긴다.
• 기저 사례와 감소하는 값을 찾아 재귀가 끝나는 이유를 확인한다.
• 호출 트리를 그려 실행 순서와 호출 횟수를 구분한다.
• 백트래킹에서 선택한 상태를 되돌리는 이유를 이해한다.
• 작은 입력의 모든 후보와 비교해 가지치기의 정확성을 검사한다.

문제 상황

작업장에서는 배송 상자를 순서대로 확인하고, 점검 장비가 서로 간섭하지 않도록 위치를 정한다. 두 작업은 겉으로는 다르지만, 현재 한 단계의 일을 처리한 뒤 나머지를 같은 방식으로 처리한다는 공통점이 있다.

첫 번째 문제는 상자별 물품 수가 주어졌을 때 전체 물품 수를 구하는 일이다. 예시 데이터는 [3, 1, 4]다. 첫 상자의 3개와 나머지 상자에 든 물품 수를 더하면 된다. 이 문제는 반복문으로 간단히 풀 수 있지만, 재귀 호출과 반환값이 연결되는 과정을 관찰하기에 알맞다.

두 번째 문제는 정사각형 점검판에 장비를 배치하는 일이다. 점검판은 n행 n열이며, 각 행에 장비를 하나씩 놓는다. 장비가 같은 열이나 같은 대각선에 있으면 신호가 간섭한다. 일부 칸은 수리 중이어서 사용할 수 없다. 가능한 전체 배치 수와 그중 처음 찾은 배치 하나를 구한다.

이 배치 규칙은 N-퀸 문제에 금지 칸을 추가한 형태다. 이 장에서는 장비를 퀸이라고 부르겠다. 행과 열은 모두 0부터 센다. 예시에서는 n이 4이고, 금지 칸은 (0, 1) 하나다. 출력할 배치는 행 순서대로 퀸의 열 번호를 나열한다. 예를 들어 (2, 0, 3, 1)은 0행의 2열, 1행의 0열, 2행의 3열, 3행의 1열에 놓았다는 뜻이다.

행마다 어느 열을 고를지 생각하면 완전 탐색의 구조가 드러난다. 아직 충돌 여부를 따지지 않으면 후보는 n의 n제곱 개다. 그러나 이미 놓은 퀸끼리 충돌한다면 뒤쪽 행을 어떻게 채워도 올바른 배치가 되지 않는다. 따라서 잘못된 부분 배치에서 탐색을 멈출 수 있다.

작은 문제를 믿고 현재 일을 처리한다

함수의 약속부터 적는다

귀납적 사고는 작은 경우에서 성립하는 사실을 이용해 그보다 큰 경우를 설명하는 방식이다. 여기서는 “남은 상자가 더 적을 때 합계를 올바르게 구할 수 있다”는 가정으로 현재 합계를 설명한다. 이 가정은 근거 없는 믿음이 아니다. 가장 작은 경우를 직접 확인하고, 큰 경우가 더 작은 경우로 이어진다는 것을 보여 주어야 한다.

상자 문제에서 함수의 약속을 “boxes의 i번 위치부터 끝까지 물품 수를 반환한다”로 정한다. 현재 값 boxes[i]에 다음 위치부터의 합계를 더하면 약속한 답이 된다. 함수 이름만 보고 막연히 이해하기보다, 인자가 가리키는 문제의 범위를 문장으로 적는 편이 좋다.

def remaining_total(boxes, i=0):
    if i == len(boxes):
        return 0
    return boxes[i] + remaining_total(boxes, i + 1)

더할 상자가 없을 때 합계는 0이다. 이처럼 더 작은 호출 없이 답을 바로 정하는 경우를 기저 사례(base case)라고 한다. 빈 리스트가 입력되어도 첫 호출에서 0을 반환한다.

물품 수 [3, 1, 4]에서 호출과 반환을 손으로 따라간 결과

단계	현재 위치	수행하는 일	반환값
호출	0	3을 남겨 두고 위치 1 호출	아직 정하지 않음
호출	1	1을 남겨 두고 위치 2 호출	아직 정하지 않음
호출	2	4를 남겨 두고 위치 3 호출	아직 정하지 않음
기저 사례	3	남은 상자가 없음	0
반환	2	4 + 0 계산	4
반환	1	1 + 4 계산	5
반환	0	3 + 5 계산	8

각 호출은 자신의 i를 따로 가진다. 안쪽 호출에서 i가 커졌다고 해서 바깥 호출의 i가 바뀌지는 않는다. 바깥 호출은 덧셈을 마치지 않은 채 기다리고, 안쪽 호출이 값을 반환하면 남겨 둔 계산을 이어 간다. 이 기다리는 호출들이 쌓이는 곳을 호출 스택(call stack)이라고 한다.

정확성과 종료를 따로 확인한다

정확성은 남은 상자 수에 대한 귀납으로 설명할 수 있다. 남은 상자가 0개이면 함수는 올바른 합계 0을 반환한다. 남은 상자가 k개일 때를 생각하자. k-1개의 합계를 재귀 호출이 올바르게 반환한다면, 현재 상자의 물품 수를 더한 값은 k개의 올바른 합계다. 따라서 기저 사례에서 시작해 모든 길이의 합계를 설명할 수 있다.

종료의 근거는 len(boxes) - i다. 처음에는 음수가 아니며, 호출할 때마다 1씩 줄어 0이 된다. 기저 사례가 있어도 그곳으로 가까워지지 않으면 실행은 끝나지 않는다. 함수가 무엇을 반환하는지와 어떤 값이 줄어드는지는 별도로 점검해야 한다.

상자가 m개이면 함수는 빈 범위를 처리하는 호출까지 m+1번 호출된다. 각 호출에서 일정한 일을 하므로 시간 복잡도는 O(m)이다. 기다리는 호출이 최대 m+1개이므로 입력 리스트를 제외한 추가 공간도 O(m)이다. 반복문으로 합계를 구하면 추가 공간을 O(1)로 줄일 수 있다. 이 문제의 재귀 구현은 실행 구조를 익히기 위한 선택이다.

호출 트리와 되돌리기로 배치를 만든다

한 행의 선택을 한 호출에 맡긴다

배치 문제에서는 함수 search(row)의 약속을 “앞의 row개 행이 올바르게 채워진 상태에서 나머지 행을 탐색한다”로 정한다. row가 n이면 모든 행을 채웠으므로 답 하나를 찾은 것이다. 그렇지 않으면 현재 행의 열을 왼쪽부터 하나씩 시도한다.

호출 트리(call tree)는 호출 하나를 점 하나로 표시하고, 그 호출이 실행한 다음 호출을 아래에 연결한 그림이다. 한 번만 재귀 호출하는 합계 문제는 길게 이어진 선이 된다. 여러 열을 시도하는 배치 문제는 가지가 갈라진다. 호출 트리의 높이와 점의 총수는 다른 양이다. 높이는 동시에 쌓이는 호출 수와 관계가 있고, 점의 총수는 전체 실행량과 관계가 있다.

퀸을 놓은 열은 cols에, 두 방향 대각선의 번호는 diag_down과 diag_up에 기록한다. 같은 대각선 위의 두 칸은 행과 열의 차 row - col이 같거나, 합 row + col이 같다. 예를 들어 (0, 2)와 (1, 3)은 차가 -2로 같으므로 충돌한다. 대각선 번호가 음수여도 집합에 저장하는 데 문제가 없다.

집합(set)은 중복 없는 값을 보관하는 자료형이다. set()으로 빈 집합을 만들고, add로 값을 넣고, remove로 지운다. 이 장에서는 이미 사용한 열과 대각선 번호가 있는지 확인하는 용도로만 쓴다.

금지 칸이 (0, 1)일 때 첫 행에서 2열을 선택한 뒤의 판단

현재 부분 배치	다음 후보	판단 근거	처리
(2,)	1행 0열	열과 두 대각선이 비어 있음	다음 행 호출
(2, 0)	2행 1열	1행 0열과 차가 같음	건너뜀
(2, 0)	2행 3열	열과 두 대각선이 비어 있음	다음 행 호출
(2, 0, 3)	3행 1열	열과 두 대각선이 비어 있음	완성 상태 호출

충돌하는 후보는 다음 행의 호출 자체를 만들지 않는다. 이런 중단을 가지치기(pruning)라고 한다. 현재 부분 배치에서 충돌이 발견되면, 뒤에 퀸을 더 놓아도 그 충돌은 없어지지 않는다. 따라서 이 가지치기는 정답을 버리지 않는다.

선택한 뒤에는 같은 상태로 돌아온다

가능한 선택을 해 보고, 더 진행할 수 없거나 답을 찾으면 선택을 되돌려 다른 후보를 시도하는 방법이 백트래킹(backtracking)이다. 퀸 하나를 놓을 때는 경로와 세 집합을 갱신한다. 재귀 호출이 돌아오면 네 곳에서 그 선택을 지운다. “선택, 다음 호출, 복구”가 한 묶음이다.

복구는 단순한 정리가 아니다. 같은 행에서 다음 열을 시험하려면 이전 열을 시험하기 전의 상태가 필요하다. 예를 들어 1행에서 0열을 시험한 뒤 그 기록을 남겨 두면, 다음 후보가 사용하지도 않은 열이나 대각선을 이미 사용한 것으로 판단하게 된다.

정확성의 기준이 되는 불변식(invariant)은 search(row)에 들어올 때마다 앞의 row개 행에 퀸이 하나씩 있고, 금지 칸과 충돌을 모두 피하며, 경로와 세 집합이 그 배치를 정확히 나타낸다는 것이다. 처음에는 아무것도 놓지 않았으므로 성립한다. 검사에 통과한 칸만 추가하므로 다음 호출에서도 성립한다. 돌아와 추가한 기록을 지우면 호출 전의 상태가 복원된다.

row가 n일 때 불변식에 의해 완전하고 올바른 배치가 만들어진다. 또한 올바른 배치의 각 행 선택은 검사에서 탈락하지 않으므로 끝까지 탐색된다. 열 순서가 정해진 배치 하나는 호출 경로도 하나뿐이어서 중복 집계되지 않는다. 이것으로 잘못된 답을 세지 않고, 올바른 답을 빠뜨리지 않음을 설명할 수 있다.

시간과 공간을 구분한다

행을 내려갈 때마다 이미 쓴 열은 다시 선택하지 않는다. 깊이 r의 부분 배치 수는 n × (n-1) × … × (n-r+1) 이하이며, 대각선과 금지 칸 검사는 이를 더 줄인다. 각 호출은 n개 열을 검사한다. 집합 연산을 평균 O(1)로 보면, n이 1 이상일 때 전체 시간의 넉넉한 상한은 O(n × n!)이다. n!은 1부터 n까지 곱한 값이다.

해를 모두 저장하지 않고 개수와 첫 해만 보관한다. 경로, 사용한 열과 대각선, 호출 스택은 각각 O(n) 공간을 쓴다. 따라서 입력을 제외한 추가 공간은 O(n)이다. 금지 칸 입력까지 포함하면 O(n + b)이며, b는 금지 칸 수다. 후보 수가 많다고 동시에 모든 후보를 메모리에 올리는 것은 아니다.

호출 횟수는 실제 탐색량을 관찰하는 지표지만 실행 시간 자체는 아니다. 이 구현은 탈락한 열도 검사하지만, 그 검사에는 호출 횟수를 더하지 않는다. 다른 구현과 수치를 비교하려면 무엇을 한 번으로 셌는지부터 맞춰야 한다.

재귀 깊이를 실행 조건으로 확인한다

Python은 지나치게 깊은 재귀 호출을 제한한다. 현재 제한값은 sys.getrecursionlimit()으로 확인할 수 있다. 제한에 이르면 RecursionError가 발생한다. 제한값은 실행 환경에 따라 확인해야 하며, 특정 숫자를 모든 환경에 공통인 상수처럼 가정하지 않는다.

합계 함수는 상자 수에 비례해 깊어진다. 배치 함수는 row가 0부터 n까지 증가하므로 탐색 함수 자체의 호출은 한 경로에서 n+1개까지 쌓인다. 실제 인터프리터에는 그 함수를 부른 바깥 호출도 있으므로 이 숫자만으로 남은 여유를 정확하게 계산할 수는 없다.

깊이 제한을 올리는 sys.setrecursionlimit()도 있지만, 값을 크게 바꾸는 것만으로 실행 자원이 확보되지는 않는다. 합계처럼 반복문으로 바로 표현되는 일은 반복문을 쓰는 편이 낫다. 길게 이어지는 탐색은 필요한 상태를 리스트에 직접 저장하는 방식도 고려할 수 있다. 이 장의 완성 코드는 n이 작은 고정 데이터만 실행하므로 제한값을 바꾸지 않는다.

깊이와 전체 호출 횟수도 구분해야 한다. 가지가 많이 갈라지는 탐색은 깊이가 작아도 전체 호출이 많을 수 있다. 반대로 합계 함수는 가지가 없지만 입력이 길면 깊이가 커진다. 실행이 느린 원인과 깊이 제한에 걸리는 원인은 같지 않다.

Python의 관련 함수는 사실 확인이 필요할 때 재귀 제한 확인 함수 설명과 재귀 제한 설정 함수 설명에서 확인할 수 있다.

완성 코드

다음 프로그램을 main.py로 저장한다. 코드 안의 문자열이 코딩 테스트의 표준 입력을 대신한다. 첫 줄은 점검판 크기와 금지 칸 수이고, 이후 줄은 금지 칸의 행과 열이다. 입력은 n이 1 이상이고, 좌표가 점검판 안에 있으며, 금지 칸이 중복되지 않는다고 가정한다.

검증용 느린 풀이는 각 행의 열 번호를 모두 만들어 검사한다. 빠른 풀이와 같은 대각선 집합을 쓰지 않고 두 퀸의 좌표를 직접 비교한다. 서로 다른 방식으로 검사하면 같은 실수를 공유할 가능성을 줄일 수 있다.

import io
from itertools import product


EXAMPLE_INPUT = """4 1
0 1
"""


def remaining_total(boxes, i=0):
    if i == len(boxes):
        return 0
    return boxes[i] + remaining_total(boxes, i + 1)


def read_problem(text):
    stream = io.StringIO(text)
    n, blocked_count = map(int, stream.readline().split())
    blocked = set()
    for _ in range(blocked_count):
        row, col = map(int, stream.readline().split())
        blocked.add((row, col))
    return n, blocked


def solve(n, blocked):
    path = []
    cols = set()
    diag_down = set()
    diag_up = set()
    solution_count = 0
    first_solution = None
    calls = 0

    def search(row):
        nonlocal solution_count, first_solution, calls
        calls += 1

        if row == n:
            solution_count += 1
            if first_solution is None:
                first_solution = tuple(path)
            return

        for col in range(n):
            down = row - col
            up = row + col

            if (row, col) in blocked:
                continue
            if col in cols or down in diag_down or up in diag_up:
                continue

            path.append(col)
            cols.add(col)
            diag_down.add(down)
            diag_up.add(up)

            search(row + 1)

            diag_up.remove(up)
            diag_down.remove(down)
            cols.remove(col)
            path.pop()

    search(0)
    return solution_count, first_solution, calls


def slow_solve(n, blocked):
    solution_count = 0
    first_solution = None

    for candidate in product(range(n), repeat=n):
        valid = True

        for row in range(n):
            if (row, candidate[row]) in blocked:
                valid = False
                break

        if not valid:
            continue

        for row in range(n):
            for previous in range(row):
                same_column = candidate[row] == candidate[previous]
                same_diagonal = (
                    abs(candidate[row] - candidate[previous])
                    == row - previous
                )
                if same_column or same_diagonal:
                    valid = False
                    break
            if not valid:
                break

        if valid:
            solution_count += 1
            if first_solution is None:
                first_solution = candidate

    return solution_count, first_solution


def verify_small_cases():
    checked = 0

    for n in range(1, 5):
        blocked_cases = [set()]
        for row in range(n):
            for col in range(n):
                blocked_cases.append({(row, col)})

        for blocked in blocked_cases:
            fast_count, fast_first, _ = solve(n, blocked)
            slow_count, slow_first = slow_solve(n, blocked)

            if (fast_count, fast_first) != (slow_count, slow_first):
                raise AssertionError(
                    f"검증 실패: n={n}, blocked={sorted(blocked)}"
                )
            checked += 1

    return checked


def main():
    boxes = [3, 1, 4]
    print(f"상자 물품 합계: {remaining_total(boxes)}")

    n, blocked = read_problem(EXAMPLE_INPUT)
    solution_count, first_solution, calls = solve(n, blocked)

    print(f"점검판 크기: {n}")
    print(f"금지 칸: {sorted(blocked)}")
    print(f"가능한 배치 수: {solution_count}")
    print(f"첫 배치: {first_solution}")
    print(f"탐색 호출 수: {calls}")

    checked = verify_small_cases()
    print(f"작은 입력 대조: {checked}개 통과")


if __name__ == "__main__":
    main()

줄별 해설

import io와 product는 각각 문자열을 입력 스트림처럼 읽는 기능과 후보 조합을 만드는 기능을 가져온다. 외부 패키지는 사용하지 않는다. product(range(n), repeat=n)은 길이가 n인 열 번호 튜플을 순서대로 만든다. 각 행의 열을 독립적으로 고르므로 열이 겹치는 후보도 포함한다.

EXAMPLE_INPUT은 실제 입력 형식을 보여 주는 문자열이다. read_problem은 readline으로 한 줄씩 읽고, split과 map으로 정수로 바꾼다. input을 호출하지 않으므로 실행 중 사용자 입력을 기다리지 않는다. 금지 칸은 좌표 튜플의 집합으로 보관한다.

remaining_total은 먼저 빈 범위를 검사한다. 리스트 원소를 읽기 전에 기저 사례를 처리해야 i가 리스트 길이와 같을 때 범위를 벗어나지 않는다. 재귀 호출에는 리스트를 잘라 전달하지 않고 위치만 전달한다. 따라서 호출마다 남은 리스트를 새로 복사하지 않는다.

solve의 첫 부분은 한 번의 문제 풀이에 필요한 상태를 만든다. 이 상태는 solve를 다시 호출할 때마다 새로 생긴다. 검증 과정에서 여러 문제를 연속으로 풀어도 앞 문제의 배치나 호출 횟수가 남지 않는다.

search 안의 nonlocal은 바깥 함수에 있는 세 변수에 새 값을 대입하겠다는 선언이다. solution_count와 calls는 정수를 증가시키고, first_solution은 처음 찾은 튜플로 바꾼다. path와 집합은 이름에 새 객체를 대입하지 않고 기존 객체의 내용을 바꾸므로 같은 선언이 필요하지 않다.

calls += 1은 함수에 들어온 직후 실행한다. 따라서 최초의 빈 배치 호출, 중간 부분 배치 호출, 완성 배치를 확인하는 호출을 모두 센다. 후보 열이 금지 칸이어서 continue로 넘어가면 새로운 호출이 없으므로 호출 횟수도 늘지 않는다.

row == n은 배치 탐색의 기저 사례다. 이곳에 도착한 경로는 이미 모든 검사를 통과했다. 배치 수를 늘리고 첫 배치가 없을 때만 저장한다. tuple(path)는 이후 path의 추가와 삭제에 영향을 받지 않는 기록을 만든다. 여기서 return해야 더 아래의 행을 처리하지 않는다.

for col in range(n)은 현재 행의 후보를 작은 열부터 확인한다. 금지 칸 검사와 세 종류의 충돌 검사를 통과한 경우에만 상태를 추가한다. 어느 집합에도 같은 번호가 없음을 확인한 뒤 넣었으므로, 복구할 때 그 번호를 지워도 이전 행의 기록을 지우지 않는다.

search(row + 1) 다음의 네 줄은 방금 한 선택을 역순으로 되돌린다. 그 결과 다음 열의 검사는 같은 출발 상태에서 시작한다. solve는 모든 가지를 살펴본 뒤 배치 수, 첫 배치, 호출 수를 반환한다. 집합 자체를 순회해 후보를 정하지 않으므로 집합의 내부 순서가 출력에 영향을 주지 않는다.

slow_solve는 n의 n제곱 개 후보를 생성한 뒤 금지 칸과 모든 퀸 쌍을 검사한다. 같은 대각선인지 여부는 두 열의 거리와 두 행의 거리가 같은지로 판단한다. n이 1 이상일 때 시간 상한은 O(n² × n의 n제곱)이며, 후보들을 한꺼번에 리스트로 만들지 않으므로 추가 공간은 O(n)이다.

verify_small_cases는 n이 1부터 4인 경우를 검사한다. 각 크기에서 금지 칸이 없는 경우와, 한 칸만 금지한 모든 경우를 만든다. 입력 수는 (1+1) + (1+4) + (1+9) + (1+16)으로 34개다. 각 입력에서는 느린 풀이가 모든 후보를 확인한다. 비교 대상은 배치 수와 첫 배치이며, 구현 방식에 따라 달라지는 호출 수는 비교하지 않는다.

두 풀이는 모두 각 행의 열을 작은 값부터 선택하므로 첫 배치도 일치해야 한다. 해가 없으면 둘 다 배치 수 0과 None을 반환한다. 이 검증은 정한 작은 입력 범위에 대한 전수 대조다. 금지 칸이 여러 개인 모든 입력까지 검사한 것은 아니며, 앞에서 제시한 불변식과 정확성 근거를 함께 사용한다.

실행 결과

macOS나 Linux에서 다음 명령으로 실행한다. 난수를 사용하지 않고 후보 순서와 출력 순서를 고정했으므로 예상 출력은 다음과 같다.

python3 main.py

상자 물품 합계: 8
점검판 크기: 4
금지 칸: [(0, 1)]
가능한 배치 수: 1
첫 배치: (2, 0, 3, 1)
탐색 호출 수: 13
작은 입력 대조: 34개 통과

호출 수 13은 손으로도 확인할 수 있다. 처음의 빈 배치가 한 번 호출된다. 첫 행의 1열은 금지되므로 나머지 0열, 2열, 3열에서만 탐색이 이어진다. 이 예시에서는 세 가지 각각에서 호출이 네 번씩 생겨 1 + 4 + 4 + 4가 된다.

첫 행이 0열인 경우의 경로는 (0,), (0, 2), (0, 3), (0, 3, 1)이다. 첫 행이 2열인 경우는 (2,), (2, 0), (2, 0, 3), (2, 0, 3, 1)이다. 첫 행이 3열인 경우는 (3,), (3, 0), (3, 0, 2), (3, 1)이다. 이 목록에는 안전해서 실제 호출로 이어진 부분 배치만 들어 있다.

한 해를 찾은 뒤에도 다른 후보를 계속 확인하므로 전체 배치 수를 셀 수 있다. 첫 해를 찾자마자 탐색 전체를 끝내는 코드로 바꾸면 첫 배치는 구할 수 있어도 전체 배치 수를 구했다는 약속은 지키지 못한다.

실무에서 자주 틀리는 것

기저 사례로 가까워지지 않는 호출

다음 코드는 i가 변하지 않아 같은 범위를 계속 호출한다. 비어 있지 않은 입력에서는 기저 사례에 도달하지 못한다.

def remaining_total(boxes, i=0):
    if i == len(boxes):
        return 0
    return boxes[i] + remaining_total(boxes, i)

다음 위치로 이동해야 남은 상자 수가 줄어든다. 인자가 달라진다는 사실만 보지 말고, 종료까지 남은 양이 줄어드는지 확인한다.

def remaining_total(boxes, i=0):
    if i == len(boxes):
        return 0
    return boxes[i] + remaining_total(boxes, i + 1)

재귀 호출 뒤에 선택을 남겨 두는 코드

다음은 경로를 관리하는 부분만 떼어 낸 코드다. 한 선택을 남겨 두면 같은 행의 다음 후보를 시험할 때 경로 길이가 맞지 않는다.

path.append(col)
search(row + 1)
# 선택을 지우지 않았다.

호출이 돌아온 뒤 선택을 지운다. 완성 코드처럼 여러 자료구조를 바꿨다면 그 자료구조도 모두 복구해야 한다.

path.append(col)
search(row + 1)
path.pop()

첫 배치를 변하는 리스트에 연결하는 코드

다음 대입은 현재 원소들의 독립된 기록을 만들지 않는다. first_solution과 path가 같은 리스트를 가리키므로, 복구 과정에서 저장한 배치도 함께 바뀐다.

if first_solution is None:
    first_solution = path

현재 내용을 별도 값으로 보관한다. 여기서는 변경하지 않을 결과라는 뜻도 드러나도록 튜플로 바꾼다.

if first_solution is None:
    first_solution = tuple(path)

호출 수와 후보 검사 수를 섞는 코드

다음 위치에서 calls를 늘리면 함수 호출이 아니라 후보 열의 검사 횟수를 세게 된다. 기저 사례의 호출도 빠진다.

def search(row):
    nonlocal calls
    for col in range(n):
        calls += 1
        # 후보 검사와 재귀 호출이 이어진다.

탐색 함수가 실행된 횟수를 세려면 함수 입구에서 한 번씩 증가시킨다. 후보 검사량도 필요하다면 이름이 다른 변수를 따로 둔다.

def search(row):
    nonlocal calls
    calls += 1
    if row == n:
        return
    for col in range(n):
        # 후보 검사와 재귀 호출이 이어진다.
        pass

한눈에 보기

재귀와 백트래킹을 설계할 때 확인할 질문

항목	확인할 질문	이 장의 배치 문제
함수의 약속	한 호출이 어떤 문제를 맡는가	앞 행의 배치를 유지하며 남은 행 탐색
기저 사례	언제 더 호출하지 않아도 되는가	row가 n일 때 배치 하나 집계
감소하는 양	종료까지 남은 양이 줄어드는가	n - row가 호출마다 1 감소
불변식	호출 입구에서 무엇이 참인가	앞 행이 안전하며 상태 기록이 일치
가지치기	버리는 가지에서 답이 나올 수 없는가	이미 생긴 충돌은 뒤의 선택으로 해소되지 않음
복구	다음 후보가 같은 출발 상태를 받는가	경로와 세 집합의 추가 내용을 삭제
호출 깊이	동시에 몇 호출이 기다리는가	탐색 함수 기준 최대 n+1개
작은 입력 대조	독립적인 풀이와 결과가 같은가	34개 입력에서 개수와 첫 배치 비교

재귀를 읽을 때 모든 호출을 머릿속에서 한꺼번에 펼칠 필요는 없다. 작은 예시는 표와 호출 트리로 따라가되, 일반적인 정확성은 함수의 약속과 불변식으로 설명한다. 코드를 작성할 때는 기저 사례, 다음 호출의 인자, 선택의 복구를 한 묶음으로 확인한다.

연습 문제

1. 물품 수가 [2, 0, 5, 1]일 때 remaining_total의 반환값과 호출 횟수를 구하라. 빈 리스트에서는 두 값이 어떻게 되는지도 설명하라.
2. 점검판이 1행 1열이고 금지 칸이 없는 경우와, (0, 0)이 금지된 경우를 비교하라. 각각의 배치 수, 첫 배치, 탐색 호출 수를 구하라.
3. 대각선 검사를 바로 앞 행의 퀸과만 수행하도록 바꾸면 어떤 문제가 생기는가. 바로 앞 행과는 충돌하지 않지만 더 앞의 행과 충돌하는 세 행의 부분 배치를 하나 제시하라.
4. verify_small_cases가 n이 1부터 3일 때 가능한 모든 금지 칸 집합을 검사하도록 바꾸는 방법을 설명하라. 총 입력 수와, 이 검증의 범위를 작게 유지해야 하는 이유를 구하라.

정답과 해설

1. 반환값은 8이고 호출 횟수는 5다. 위치 0, 1, 2, 3을 처리하는 호출과 위치 4의 빈 범위를 처리하는 호출이 있다. 물품 수가 0인 상자도 한 위치이므로 호출을 생략하지 않는다. 빈 리스트에서는 최초 호출이 곧 기저 사례이므로 반환값은 0이고 호출 횟수는 1이다.

2. 금지 칸이 없으면 search(0)이 퀸을 놓고 search(1)을 호출한다. 따라서 배치 수는 1, 첫 배치는 (0,), 호출 수는 2다. (0, 0)이 금지되어 있으면 최초 호출에서 유일한 후보를 건너뛴다. 배치 수는 0, 첫 배치는 None, 호출 수는 1이다. 해가 없어도 탐색을 시작한 호출은 센다.

3. 서로 이웃하지 않은 행에서도 대각선 충돌이 생긴다. 예를 들어 크기 4인 판의 부분 배치 (0, 3, 2)를 보자. 0행 0열과 1행 3열은 충돌하지 않는다. 1행 3열과 2행 2열도 행 거리는 1, 열 거리는 1이므로 충돌한다. 따라서 이 후보는 요구한 반례가 되지 않는다. 반례는 검사를 직접 해 보며 골라야 한다.

   조건에 맞는 부분 배치는 (0, 3, 0)이다. 이웃한 행끼리는 열이 다르고 열 거리 3이 행 거리 1과 다르지만, 0행과 2행이 같은 열이다. 대각선 검사만의 오류를 보이려면 (0, 3, 2) 대신 크기 5인 판의 (0, 4, 2)를 사용하면 된다. 이웃한 행의 열 거리는 각각 4와 2이므로 대각선 충돌이 없다. 그러나 0행 0열과 2행 2열은 행 거리와 열 거리가 모두 2여서 충돌한다. 열도 모두 다르므로 앞 행만 확인하는 대각선 검사의 누락을 분명히 보여 준다.

4. 각 칸에 대해 “금지하지 않음”과 “금지함”을 선택하면 된다. product((False, True), repeat=n * n)으로 모든 선택을 만들고, True인 위치를 좌표로 바꾼다. 일렬 위치 k의 좌표는 (k // n, k % n)이다. 각 크기의 입력 수는 2의 n²제곱이므로 총수는 2 + 16 + 512로 530개다.

   for n in range(1, 4):
       for flags in product((False, True), repeat=n * n):
           blocked = {
               (k // n, k % n)
               for k, is_blocked in enumerate(flags)
               if is_blocked
           }
           fast_count, fast_first, _ = solve(n, blocked)
           slow_count, slow_first = slow_solve(n, blocked)
           if (fast_count, fast_first) != (slow_count, slow_first):
               raise AssertionError("검증 실패")

   금지 칸 집합 수 자체가 빠르게 늘고, 각 입력에서 느린 풀이가 n의 n제곱 개 후보를 확인한다. 따라서 작은 크기에서 입력까지 전수 생성하고, 더 큰 크기에 대한 설명은 불변식과 귀납적 근거로 이어 가는 편이 적절하다.