[python 구현]DFS에서 꼭 필요한 개념 - 조합 (combination)

 

 

 

N개중에서 r개를 뽑는 경우를 어떻게 구할까?

 

바로 조합을 이용하면 구할 수 있다.

조합은 중복을 허락하지않고 순서를 생각하지 않는다. 

 

 

 

 

n = 4, m = 2 

아래 사진이 4까지의 숫자에서 2자리 수를 출력하는 코드의  상태트리이다. 

 

 

 

 

D(0,1)에서 처음 시작한다.

0은 level을 1은 start를 의미한다. 

 

 

 

 

 

 

 

 

 

출력할 숫자를 담을 배열을 res라고 하자 (크기는 m 만큼이다.)

 

 

 

 

 

 

두번째 인수(start)보다 크거나 같은 수를 res 배열의 level 자리수에 넣어가며 for문을 돌린다.

즉, 위와 같은 경우 res는 0,1 index만 존재하기 때문에 level이 2가 종료 조건이다. 

 

 

 

첫번째 인수는 Level이므로 한단계씩 진행됨에 따라 1씩 증가시킨다. 

두번재 인수는 res에 들어간 수에서 1을 증가시켜 DFS를 호출한다. 이렇게 해야 이미 res에 들어간 수와 중복이 안된다.

 

 

 

 

반복하며 DFS의 첫번째 인수가 구해야할 숫자의 길이와 동일해지면 그때의 res값을 출력한후 DFS를 멈춘다.

 

 

 

 

 

 4와 2를 입력받고 조합의 경우와 경우의 수를 출력하는 코드는 

 

n,r = map(int,input().split())
res = [0]*r
cnt = 0
def dfs(L,s) :
    global cnt
    if L == r :
        for i in res :
            print(i,end='')
        print()
        cnt+=1
    else :
        for v in range(s,n+1) :
            res[L] = v  # v는 지금 들어갔으므로
            dfs(L+1, v+1) # v 다음부터 들어가기 위해 
dfs(0,1) 
print(cnt)

 

 

 

조합의 개수를 구하는 법은 

4C2의 경우 (4*3) // (1*2)를 하면 된다. 

다른 예로는 5C3을 하면 이것은 5C2와 같고 이는 (5*4)// 2 이므로 10이다. 

 

이유는 모르겠는데 자동으로 이렇게 계산방법이 생각났다. 아마 고등학교때 배웠었을 것이다.  

 

 

 

참고 :

인프런_김태원 파이썬 알고리즘 문제풀이 _조합