BackTracking

백트래킹

현재 상태에서 가능한 모든 경로를 따라 탐색하다가 원하는 값이 아니면 더 이상 탐색을 진행하지 않고 전 단계로 돌아감.

백트래킹 특징

• 가지치기 사용가능(유망하지 않으면 탐색x)
• 기본적으로 재귀의 성격을 띄는 형태

백트래킹과 DFS차이

• DFS는 모든 경로를 탐색하지만 백트래킹은 불필요한 경로를 조기에 차단함
• DFS나 백트래킹의 최악의 경우 지수함수 시간을 요하지만 평균적으로 백트래킹의 속도가 더 빠름

code

부분수열의 합

def back(start):
    global cnt
    if sum(stack) == s and len(stack) >0:
        cnt +=1
       

    for i in range(start, n):
        stack.append(li[i])
        back(i+1)
        stack.pop()

n , s = map(int, input().split())
li = list(map(int, input().split()))
cnt = 0
stack =[]

back(0)
print(cnt)

차이를 최대로

def back():
    global ans
    if sum(visited) ==n:
        total = 0
        for i in range(n-1):
            total += abs(stack[i]-stack[i+1])

        if total > ans:
            ans =total

            return


    for i in range(n):
        if visited[i]==0:
            visited[i]=1
            stack.append(li[i])
            back()
            stack.pop()
            visited[i]=0


n = int(input())
li = list(map(int, input().split()))
visited= [0] *n
stack=[]
ans =0

back()
print(ans)

최소생산비용 (SWEA)

T= int(input())

def back(product,idx):
    global min
    if product > min:
        return 
    if sum(visited) == n:
        if product < min:
            min = product
        return

    for i in range(n):
        if visited[i]==0:
            visited[i]=1
            back(li[idx][i]+product,idx+1)
            visited[i]=0

for tc in range(1, T+1):
    n = int(input())
    li= [list(map(int,input().split())) for _ in range(n)]
    stack=[]
    min =0
    for i in range(n):
        min += sum(li[i])
    visited=[0]*n
    back(0,0)
    print(f'#{tc} {min}')