[파이썬으로 배우는 알고리즘 기초] 5. 백트래킹

5-0. 백트래킹(Backtracking)

• 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는 데 적합
• 1. 상태공간트리를 깊이우선탐색(Depth First Search)으로 탐색
       - 상태공간트리(State Space Tree): 해답을 탐색하기 위한 탐색 공간을 트리 형태의 구조로 암묵적으로 해석한 것
  2. 방문 중인 노드에서 더 하위 노드로 가서 해답이 없을 경우(유망하지 않을 경우), 하위 트리를 방문하지 않고 부모 노드로 되돌아감 + 하위 트리는 가지치기(pruning)

---

5-1. N-Queens 문제

• N * N 체스보드에 N개의 퀸을 배치하는 문제
• 어떤 퀸도 다른 퀸에 의해서 잡아먹히지 않도록 배치해야 함. 즉, 같은 행 / 열 / 대각선에는 다른 퀸을 놓을 수 없음
• 임의의 집합: 체스보드에 있는 N^2개의 가능한 위치
  기준: 새로 놓을 퀸이 다른 퀸을 위협하면 안 됨
  원소의 순서: 퀸을 놓을 수 있는 N개의 위치

def promising(i, col):
    k = 1
    flag = True
    while k < i and flag:
        if (col[i] == col[k]) or (abs(col[i] - col[k]) == (i - k)):
            flag = False
        k += 1
    return flag

def n_queens(i, col):
    N = len(col) - 1
    if promising(i, col):
        if i == N:
            print(col[1: N + 1])
        else:
            for j in range(1, N + 1):
                col[i + 1] = j
                n_queens(i + 1, col)

N = 4
col = [0] * (N + 1)
n_queens(0, col)

---

5-2. 부분집합의 합 구하기

• 원소가 N개인 양의 정수 집합 w와 양의 정수 W가 주어졌을 때, 합이 W가 되는 w의 부분집합을 모두 구하기
• 원소를 오름차순으로 정렬하면 각 노드가 유망한지 여부를 알 수 있음
  - i번째 레벨에서 wi+1은 남아 있는 정수 원소 중 가장 작은 값
  - 레벨 i까지의 모든 정수 원소의 합을 weight라고 할 때, weight에 wi+1를 더해서 W보다 클 경우 가지치기
  - weight에다 남은 정수 원소의 합 total을 더해서 W보다 작을 경우에도 가지치기

def promising(i, weight, total):
    if (weight + total >= W) and (weight == W or weight + w[i+1] <= W):
        return True
    else:
        return False

def sum_of_subsets(i, weight, total):
    N = len(w) - 1
    if promising(i, weight, total):
        if weight == W:
            print(include[1:N + 1])
        else:
            include[i + 1] = True
            sum_of_subsets(i + 1, weight + w[i + 1], total - w[i + 1])
            include[i + 1] = False
            sum_of_subsets(i + 1, weight, total - w[i + 1])

W = 21
w = [0, 5, 6, 10, 11, 16]
total = sum(w)
include = [False] * (len(w))
sum_of_subsets(0, 0, total)

 

 

 

※ 강의 링크: https://inf.run/v8Rn