[Python] 6장 백트래킹&상태트리&DFS 내용 정리

• [선수지식] 재귀함수와 스택

# ch6 - [선수지식] 재귀함수와 스택
def DFS(x):
    if x > 0:
        DFS(x-1)
        print(x)  # 1 2 3

        #print(x) # 3 2 1 -> stack에 매개변수, 지역변수, 복귀주소 저장
        #DFS(x-1)

if __name__ == "__main__":
    n = int(input())
    DFS(n)

 

• 1. 재귀함수를 이용한 이진수 출력

# ch6 - 1. 재귀함수를 이용한 이진수 출력
n = 720

def recursive(num):
    if num >= 1:
        recursive(num//2)
        print(num%2, end='')
recursive(n)

 

• 2. 이진트리 순회(깊이우선탐색)

# ch6 - 2. 이진트리 순회(깊이우선탐색)
# 깊이우선탐색은 root부터 탐색 -> 전위순회

def DFS(n):
    if n>7:
        return
    
    else:
        left = n*2
        right = (n*2)+1
        print(n, end=' ')
        DFS(left)
        DFS(right)
DFS(1)

 

• 3. 부분집합 구하기

# ch6 - 3. 부분집합 구하기
n = 3
ch=[0]*(n+1)

def DFS(v):
    if v>n:
        for i in range(1, n+1):
            if ch[i]==1:
                print(i, end=' ')
        print()
    else:
        # D(1) -> D(2) -> D(3)
        ch[v]=1 # 방문 체크
        DFS(v+1)
        ch[v]=0
        DFS(v+1)
DFS(1)

 

• 4. 합이 같은 부분집합

# ch6 - 4. 합이 같은 부분집합

n = 6
list = [1,3,5,6,7,10]
total = sum(list)

def DFS(v,sum):
    if v==n:
        if sum==(total-sum): 
            print('YES')
    else:
        DFS(v+1, sum+list[v])
        DFS(v+1, sum)
DFS(0,0)

 

• 5. 바둑이 승차

# ch6 - 5. 바둑이 승차
c, n  = 259, 5 # 제한 무게, 바둑이 수
list = [81,58,42,33,61]
maxVal =float('-inf')

def DFS(v,sum):
    global maxVal
    if n==v:
        if sum>maxVal and c>=sum:
            maxVal=sum
    else:
        DFS(v+1, sum+list[v])
        DFS(v+1, sum)
DFS(0,0)
print(maxVal)

 

• 6. 중복 순열 구하기

# ch6 - 6. 중복 순열 구하기
n, m = 3,2
res = [0]*m
cnt = 0

def DFS(v):
    global cnt 
    if v==m: 
        for j in res:
            print(j, end=' ') # 배열안에 있는 수열 출력
        print()
        cnt = cnt + 1
    else:
        # 중복 상관없이 d1, d2, d3
        for i in range(1, n+1):
            res[v] = i # 배열에 수열 넣기
            DFS(v+1)

DFS(0)
print(cnt)

 

• 7. 동전 교환 - 복습

# ch6 - 7. 동전 교환
n=3 # 동전 종류 개수
list=[1,2,5] # 동전 종류
m = 15 # 거스름돈
minCnt = float('inf')
cnt = 0

def DFS(v,sum):
    global minCnt
    if v>minCnt or sum>m: # 최소개수를 넘거나 거스름돈 초과하면 종료
        return
    if sum == m and v < minCnt: # 거스름돈 가격일 때, 최소 개수
        minCnt = v
    else:
        for i in range(n): # d0->d1->d2..., 각 가격
            DFS(v+1, sum+list[i])

DFS(0,0)
print(minCnt)

 

• 8. 순열 구하기

# ch6 - 8. 순열 구하기
n, m = 3,2
cnt = 0
res = [0]*n
ch = [0]*(n+1)

def DFS(v):
    global cnt
    if v==m: # 순열 길이만큼 
        for i in range(n): # 결과 출력
            print(res[i], end=' ')
        print()
        cnt = cnt + 1
    else:
        for j in range(1, n+1):
            if ch[j]==0: # 방문 안한경우
                ch[j] = 1 # 방문체크
                res[v]= j 
                DFS(v+1)
                ch[j] = 0
                
DFS(0)
print(cnt)

 

• 9-1. 순열 추측하기 - 복습

# ch6 - 9. 수열 추측하기
import sys
n, f = 4, 16

p = [0]*n
b = [1]*n # 1 1 1 1 -> 1 3 3 1
ch = [0]*(n+1)

def DFS(v, sum):
    if v==n and sum==f:
        for j in p:
            print(j, end=' ')
        sys.exit(0)
    else:
        for i in range(1, n+1):
            if ch[i]==0:
                ch[i]=1
                p[v]=i
                DFS(v+1, sum+(p[v]*b[v]))
                ch[i]=0

for i in range(1, n): # 맨끝은 x
    b[i] = b[i-1]*(n-i)//i # 이항계수 구하기

DFS(0,0)

 

• 9-2. 순열 추측하기(라이브러리)

#ch6 - 10. 수열 추측하기(라이브러리)
import sys
import itertools as it
n, f = 4, 16
b=[1]*n
cnt = 0

for i in range(1,n):
    b[i] = b[i-1]*(n-i)//i # 이항계수

a = list(range(1,n+1))

# 모든 수열의 경우의 수 구해주는 permutations
for tmp in it.permutations(a):
    sum = 0
    for L, x in enumerate(tmp):
        sum = sum + (x*b[L])
    if sum==f:
        for x in tmp:
            print(x, end=' ')
        break

#4개의 수 중에서 3개의 수로 수열만드는 경우
#for tmp in it.permutations(a, 3):
#    print(tmp)

 

• 10. 조합구하기 - 복습

# ch6 - 10. 조합 구하기
n, m = 4, 2
cnt = 0
res = [0]*m

def DFS(v, start):
    global cnt
    if v==m:
        for j in res:
            print(j, end=' ')
        print()
        cnt = cnt + 1
    else:
        for i in range(start,n+1): # 시작지점부터
            res[v]=i
            DFS(v+1, i+1)

DFS(0, 1)
print(cnt)

 

• 11-1. 수들의 조합

# ch6 - 11. 수들의 조합(dfs)
n, k = 5, 3
list = [2, 4, 5, 8, 12]
m = 6
cnt = 0

def DFS(v, sum, start):
    global cnt
    if v == k and sum % m == 0:
        cnt = cnt + 1
    else:
        for i in range(start, n):
            DFS(v+1, sum+list[i], i+1)

DFS(0, 0, 0)
print(cnt)

 

• 11-2. 수들의 조합(라이브러리)

# ch6 - 11. 수들의 조합(라이브러리) 
import sys
import itertools as it
n, k = 5, 3
a = [2, 4, 5, 8, 12]
m=6
cnt = 0

for x in it.combinations(a, k): # a 리스트에서 k개의 조합
    if sum(x)%m==0:
        print(x)
        cnt = cnt + 1
print(cnt)

 

• 12. 인접행렬(가중치 방향 그래프)

# ch6 - 12. 인접행렬(가중치 방향그래프)
n,m=6,9 # 정점의 수, 간선의 수
# 연결정보 거리비용
list=[[1,2,7],[1,3,4],[2,1,2],[2,3,5]
,[2,5,5],[3,4,5],[4,2,2],[4,5,5],[6,4,5]]
res = [[0]*(n+1) for _ in range(n+1)] # 2차원 배열 생성 0으로 초기화

for i in range(len(list)):
    # a, b, c = map(int, input().spilt())
    start = list[i][0]
    end = list[i][1]
    cost = list[i][2]
    res[start][end]=cost

for i in range(1, n+1):
    for j in range(1, n+1):
        print(res[i][j], end= ' ')
    print()

 

• 13. 경로 탐색 - 복습

# ch6 - 13. 경로 탐색
n, m = 5, 9  # 정점의 수, 간선의 수
list = [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]]
info = [[0]*(n+1) for _ in range(n+1)]  # 2차원 배열 생성
cnt = 0
ch = [0]*(n+1)

for i in range(len(list)):
    start = list[i][0]
    end = list[i][1]
    info[start][end] = 1

def DFS(L):
    global cnt
    if L == n:
        cnt += 1
        for x in path:
            print(x, end=' ')
        print()
    else:
        for i in range(1, n+1):
            if info[L][i] == 1 and ch[i] == 0:
                ch[i] = 1
                path.append(i)
                DFS(i)
                path.pop()
                ch[i] = 0

path = []
path.append(1)
ch[1] = 1
DFS(1)
print(cnt)