Algorithm - 조합 구하기(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[조합 구하기(DFS)]

 

1부터 N까지 번호가 적힌 구슬이 있다.

N개의 구슬 중 M개의 구슬을 뽑는 경우의 수를 출력하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 자연수 N(3 ≤ N ≤ 10)과 M(2 ≤ M ≤ N)이 주어진다.

 

*출력 설명

첫 번째 줄부터 차례대로 결과 값을 출력한다.

맨 마지막 줄에는 총 경우의 수를 출력한다.

단, 출력순서는 사전순으로 오름차순으로 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_52.txt', 'rt')

def DFS(L, s):
    global cnt
    if L == m:
        for j in range(L):
            print(res[j], end=' ')
        cnt += 1
        print()
    else:
        for i in range(s, n+1):
            res[L] = i
            DFS(L+1, i+1)

if __name__ == "__main__":
    n, m = map(int, input().split())
    res = [0] * (n+1)
    cnt = 0
    DFS(0, 1)
    print(cnt)
    
''' 
출력 :
1 2 
1 3 
1 4 
2 3 
2 4 
3 4 
6

'''

 

input_52.txt(입력)

4 2

 

 

중요내용

1. DFS() 함수의 인자 L은 상태트리의 레벨을 의미한다.
2. DFS() 함수의 인자 s는 조합의 구성 값(구슬 번호)을 의미한다.
3. 참고로, DFS(L+1, i+1) 코드에서 두 번째 인자 값이 i+1인 이유는 구슬 번호의 중복을 피하기 위함이다.
4. 리스트 변수 res는 조합의 결과를 저장하기 위해 사용된다.
5. DFS() 함수 안에서 변수 cnt를 재정의했기 때문에 해당 변수는 지역변수가 되므로 global cnt 코드를 작성해줘야 한다. (해당 변수를 전역변수로 만들어줘야 함)