[알고리즘] 기본 개념 정리 (7) - 백트래킹을 이용한 해의 탐색과 그 실제

백트래킹을 이용한 해의 탐색과 그 실제

• 조합 및 순열 문제: 서로 다른 요소들의 모든 조합이나 순열을 생성할 때 사용됩니다.
• N-Queens 문제: N×N 체스판 위에 N개의 퀸을 서로 공격할 수 없게 배치하는 문제를 해결할 때 사용됩니다.
• 수도쿠: 주어진 조건을 만족하는 수도쿠 보드를 완성하는 데 사용됩니다.
• 그래프 색칠 문제: 그래프의 정점을 최소한의 색상으로 색칠하는 방법을 찾는 문제 해결에 사용됩니다.

백트래킹과 효율적 해 탐색

Q - 여섯 명을 중복 없이 한 명씩 나열하는 경우를 모두 출력하는 프로그램?

→ 6^6 중, 중복되지 않는 경우만 추출해 나열 vs 중복된 수를 제외하면서 나열

Backtracking

• 가능한 모든 해를 탐색, 조건에 어긋나는 경우 이전으로 돌아가는 기법
• 어떤 지점이 해의 조건에 위배 → 그 경우를 제외
• 완전 탐색 알고리즘보다 효율적인 성능 기대 가능
• Tree에서 ‘깊이 우선 탐색’와 깊은 관련이 있음

member = ['Rei', 'Gaeul', 'Leeseo', 'Liz']
line = list()

for i in range(0, len(member)):
    line.append('')

def line_up(num):
    if (check(num)):
        if (num == len(member)):
            print(line)
        else:
            for i in range(0, len(member)):
                line[num] = member[i]
                line_up(num + 1)

def check(num):
    if num == 0:
        return True
    target = line[num - 1]
    for each_member in line[0:(num - 1)]:
        if (each_member == target):
            return False
    return True

line_up(0)

N-Queen 문제와 백트래킹

Q - NxN 체스판 구조에서 대각선으로 겹치지 않도록 하는 프로그램?

N = 4
spr = list()

for i in range(0, N):
    spr.append(-1)

def spr_up(num):
    if (check(num)):
        if (num == N):
            print(spr)
        else:
            for i in range(0, N):
                spr[num] = i
                spr_up(num + 1)

def check(num):
    for k in range(0, num - 1):
        if (spr[num-1] == spr[k]):
            return False
        elif (abs(spr[num-1] - spr[k]) == (num - 1 - k)):
            return False
    return True

조합에서의 백트래킹 응용

Q - 블랙잭 게임

card = [3, 7, 9, 5, 1, 8, 4]
target = 21

def blackjack(num, choose):
    if (check(choose) == 'UNDER'):
        if (num < len(card)):
            blackjack(num + 1, choose)
            blackjack(num + 1, choose + [card[num]])
    elif (check(choose) == 'BLACKJACK'):
        print(choose)

def check(choose):
    if (sum(choose) < traget):
        return 'UNDER'
    elif (sum(choose) == traget):
        return 'BLACKJACK'
    else:
        return 'OVER'

blackjack(0, list())

Python에서의 순열과 조합

itertools를 이용한 순열의 구성

from itertools import permutations

member = ['Rei', 'Gaeul', 'Leeseo', 'Liz', 'Yujin', 'Wonyoung']

for each_p in permutations(member, 6):
    print(each_p)

itertools를 이용한 조합의 구성

from itertools import combinations

card = [3, 7, 9, 5, 1, 8, 4]

for each_c in combinations(card, 5):
    print(each_c)