[Algorithms] 완전탐색(백트랙킹, 상태트리와 CUT EDGE)/깊이우선탐색(DFS) Basic-조합 구하기(DFS)

 

 

 

• 앞의 순열 구하기 문제와 다른 점은 previous level에 있는 값 보다 current level에 있는 값이 더 커야 한다는 것
• 그 점을 생각해서 코드를 작성했었다 - 내가 한 풀이 방식 같은 경우는 중복된 수가 이미 나왔는지 검사하는 check list 가 필요했고, 이전 레벨의 값이 현재보다 큰지 검사하는 조건절도 필요했다

def DFS(level):
    global cnt
    if level==m:
        for x in arr:
            print(x, end=" ")
        print()
        cnt+=1
    else:
        for i in range(1, n+1):
            if ch_ls[i]==0:
                if level!=0:
                    if arr[level-1] > i:    # 이전 레벨의 값이 현재 보다 크다면
                        continue            # 지나간다
                ch_ls[i]=1
                arr[level]=i
                DFS(level+1)
                ch_ls[i]=0
 
if __name__=='__main__':
    n, m = map(int, input().split())
    ch_ls=[0]*(n+1)
    arr=[0]*m
    cnt=0
    DFS(0)
    print(cnt)
 

 

• 인프런 강의에서 나온 문제 풀이 방식 - start 지점을 인자로 전달해서 거기서부터 트리 줄기를 뻗어나간다. 따라서, 이미 중복된 수가 들어갔는지 검사하는 check list가 필요가 없다. start 지점이 이미 전 값보다 큰 상태에서 출발하기 때문에 조건절을 추가 할 필요도 없다.

import sys
# sys.stdin=open("input", "r")
input=sys.stdin.readline    # 입력양이 많을 때 이 라인을 쓰면 입력 속도가 빨라진다
# s=input().rstrip()        # 위의 라인을 사용하게 되면 문자열을 읽을 때 줄바꿈 기호가 들어오므로 이를 날려야한다
 
def DFS(level, start):
    global cnt
 
    if level==m:
        for x in res:
            print(x, end=' ')
        print()
        cnt+=1
    else:
        for i in range(start, n+1):
            res[level]=i
            DFS(level+1, i+1)
 
if __name__=='__main__':
    n, m = map(int, input().split())
    res = [0]*m
    cnt = 0
    DFS(0, 1)
    print(cnt)