SW 백트래킹 미로찾기

def checknode (v) : #node
	if promising(v):
		if there is a solution at v :
        	write the solution
        else :
        	for u in each child of v :
            	checknode(u)

power Set 

어떤 집합의 공집합과 자기자신을 포함한 모든 부분집합

구하고자 하는 어떤 집합의 원소 개수가 n 일 경우 부분집합의 개수는 2 ^n 이나옴

 

### 백트래킹 방법

def backtrack(a, k, input) :
	global MAXCANDUDATES
    c = [0]*MAXCANDIDATES
    
    if k = input :
    	process_solution(a, k)
    else:
    	k+=1
        ncandidates = construct_candidates(a, k, input, c)
        for i in range(ncandidates):
        	a[k] = c[i]
            backtrack(a,k,input)

def construck_candidates(a, k, input, c):
	c[0] = True
    c[1] = False
    return 2
    
MAXCANDIDATES = 100
NMAX = 100
a = [0] * NMAX
backtrack(a, 0, 3)

### 순열백트래킹

def backtrack(a, k, input) :
	global MAXCANDUDATES
    c = [0]*MAXCANDIDATES
    
    if k = input :
    	for i in range(1,k+1):
        	print(a[i], end=" ")
        print()
    else:
    	k+=1
        ncandidates = construct_candidates(a, k, input, c)
        for i in range(ncandidates):
        	a[k] = c[i]
            backtrack(a,k,input)

def construck_candidates(a, k, input, c):
	in_perm = [False]*NMAX
    
    for i in range(1,k):
    	in_perm[a[i]] = True
        
    ncandidates = 0 
    for i in range(1, input+1):
    	if in_perm[i] == False:
        	c[ncandidates] = i
            ncandidates += 1
        return ncandidates