백트래킹

백트래킹이란?

해를 찾아가는 도중 결과 값이 도출될 것 같지 않으면 과정을 중단하고 되돌아 가는 과정

• 완전 탐색 방법 중 하나인 깊이 우선 탐색(DFS)를 진행하면서 조건을 확인하고 해당 노드가 유망하지 않으면 탐색을 중단 -> 이는 반복문의 횟수를 줄일 수 있으므로 효율적이다.

백트래킹 기법의 유망성 판단법

• 유망하다(promising) : 해가 될 가능성이 있으면 유망하다라고 판단
• 가지치기(pruning) : 유망하지 않는 노드에 가지 않는 것을 말함

백트래킹과 DFS의 차이

백트래킹 : 불필요한 탐색을 하지 않는다.
DFS : 모든 경우의 수를 탐색한다.

백트래킹을 이용한 백준 문제 리스트

1.N과 M

import sys
n,m=map(int,sys.stdin.readline().split())

s=[]

def dfs():
    if len(s)==m:
        print(' '.join(map(str,s)))
        return 

    for i in range(1,n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
dfs()

2.부분 수열의 합

import sys
n,s = map(int,sys.stdin.readline().split())
list1=list(map(int,sys.stdin.readline().split()))


cnt=0
def dfs(idx,result):
    global cnt
    if sum(result)==s and len(result)!=0:
        cnt+=1

    for i in range(idx,n):
        result.append(list1[i])
        dfs(i+1,result)
        result.pop()

dfs(0,[])
print(cnt)

3.N-QUEEN

import sys
n=int(sys.stdin.readline())
cnt=0

pos= [0]*n #각 열에 배치한 퀸의 위치
flag_a = [False]*n #각 행에 퀸을 배치했는지 체크
flag_b = [False]*(n*2-1) #대각선 방향으로 퀸을 배치했는지 체크
flag_c = [False]*(n*2-1)  #대각선 방향으로 퀸을 배치했는지 체크
list1=[]

def set(i):
    for j in range(n):
        cnt=0
        if not flag_a[j] and not flag_b[i+j] and not flag_c[i-j+(n-1)]:
            pos[i]=j
            if i==n-1:
                #put()
                cnt+=1
                list1.append(cnt)
            else:
                flag_a[j]= flag_b[i+j] = flag_c[i-j+(n-1)] = True
                set(i+1)
                flag_a[j] = flag_b[i+j] = flag_c[i-j+(n-1)]=False


set(0)
print(sum(list1))

---

참고 :

1. https://veggie-garden.tistory.com/24