구현

이 장에서는 Python으로 부분집합, 순열, N-Queens를 구현하고 한 줄씩 설명합니다. 이어서 N-Queens 해의 개수를 세는 같은 핵심 루틴을 C++, Java, TypeScript로 옮깁니다. 언어가 달라도 구조는 선택, 탐색, 되돌리기 세 줄로 똑같습니다.

부분집합과 순열 (Python)

def subsets(nums):
    result, path = [], []

    def dfs(start):
        result.append(path[:])            # 모든 노드가 하나의 부분집합
        for i in range(start, len(nums)):
            path.append(nums[i])          # 선택
            dfs(i + 1)                    # 탐색: i 뒤만 고른다
            path.pop()                    # 되돌리기

    dfs(0)
    return result


def permutations(nums):
    result, path = [], []
    used = [False] * len(nums)

    def dfs():
        if len(path) == len(nums):        # 리프: 순열 하나 완성
            result.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:                   # 이미 쓴 원소는 건너뜀
                continue
            used[i] = True
            path.append(x)
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return result

• subsets는 리프가 아니라 모든 노드에서 결과를 저장합니다. start부터만 고르기 때문에 [1, 2]와 [2, 1]이 둘 다 생기지 않습니다.
• permutations는 순서가 중요하므로 매번 처음부터 훑되, used 배열로 이미 고른 원소를 막습니다. used[i] = False가 되돌리기의 짝입니다.
• 두 함수 모두 path[:]로 복사해 저장합니다.

N-Queens (Python)

def solve_n_queens(n):
    cols, diag, anti = set(), set(), set()
    queens, boards = [], []

    def place(row):
        if row == n:                                   # 모든 행에 놓음
            boards.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
            return
        for c in range(n):
            if c in cols or row - c in diag or row + c in anti:
                continue                               # 가지치기
            cols.add(c); diag.add(row - c); anti.add(row + c)
            queens.append(c)
            place(row + 1)
            queens.pop()
            cols.remove(c); diag.remove(row - c); anti.remove(row + c)

    place(0)
    return boards

for line in solve_n_queens(4)[0]:
    print(line)
# .Q..
# ...Q
# Q...
# ..Q.

• 한 행에 퀸을 하나씩 놓으므로 row가 깊이입니다.
• cols, diag(row - c), anti(row + c) 세 집합으로 충돌 검사를 O(1)에 끝냅니다. 앞 장의 is_safe처럼 매번 모든 퀸을 훑으면 O(n)이 듭니다.
• 선택할 때 세 집합에 넣고, 돌아올 때 같은 값을 빼야 다른 가지가 깨끗한 상태에서 시작합니다.

N-Queens 해의 개수 (C++)

다른 언어에서는 해를 세기만 하는 같은 루틴을 보여 줍니다. 열과 대각선 번호가 작은 정수이므로 집합 대신 불리언 배열을 씁니다.

#include <iostream>
#include <vector>

int n;
std::vector<bool> col, diag, anti;

int place(int row) {
    if (row == n) return 1;
    int count = 0;
    for (int c = 0; c < n; ++c) {
        if (col[c] || diag[row - c + n - 1] || anti[row + c]) continue;
        col[c] = diag[row - c + n - 1] = anti[row + c] = true;
        count += place(row + 1);
        col[c] = diag[row - c + n - 1] = anti[row + c] = false;
    }
    return count;
}

int main() {
    n = 8;
    col.assign(n, false);
    diag.assign(2 * n - 1, false);
    anti.assign(2 * n - 1, false);
    std::cout << place(0) << "\n";  // 92
}

row - c는 음수가 될 수 있으므로 n - 1을 더해 0부터 2n - 2까지의 배열 인덱스로 바꿉니다.

N-Queens 해의 개수 (Java)

public class NQueens {
    static int n;
    static boolean[] col, diag, anti;

    static int place(int row) {
        if (row == n) return 1;
        int count = 0;
        for (int c = 0; c < n; c++) {
            if (col[c] || diag[row - c + n - 1] || anti[row + c]) continue;
            col[c] = diag[row - c + n - 1] = anti[row + c] = true;
            count += place(row + 1);
            col[c] = diag[row - c + n - 1] = anti[row + c] = false;
        }
        return count;
    }

    public static void main(String[] args) {
        n = 8;
        col = new boolean[n];
        diag = new boolean[2 * n - 1];
        anti = new boolean[2 * n - 1];
        System.out.println(place(0)); // 92
    }
}

N-Queens 해의 개수 (TypeScript)

function countNQueens(n: number): number {
  const col = new Array<boolean>(n).fill(false);
  const diag = new Array<boolean>(2 * n - 1).fill(false);
  const anti = new Array<boolean>(2 * n - 1).fill(false);

  const place = (row: number): number => {
    if (row === n) return 1;
    let count = 0;
    for (let c = 0; c < n; c++) {
      const d = row - c + n - 1;
      if (col[c] || diag[d] || anti[row + c]) continue;
      col[c] = diag[d] = anti[row + c] = true;
      count += place(row + 1);
      col[c] = diag[d] = anti[row + c] = false;
    }
    return count;
  };

  return place(0);
}

console.log(countNQueens(8)); // 92

정리

• 부분집합은 모든 노드에서, 순열과 N-Queens는 리프에서 결과를 저장합니다.
• 충돌 검사를 집합이나 배열로 바꾸면 한 번의 검사가 O(1)이 됩니다.
• 선택할 때 바꾼 상태는 돌아올 때 정확히 같은 순서로 되돌려야 합니다.