파이썬 알고리즘 문제풀이 입문] 완전탐색 (백트랙킹, 상태트리와 CUT EDGE) / DFS(깊이우선탐색) 기초 - 조합 구하기 (DFS)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.

 

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

def DFS(index, start):
    global count, delete_num

    if index == M:
        for i in range(M):
            print(c[i], end=' ')
        count += 1
        print()
    else:
        for i in range(start, N+1):
            c[index] = i
            DFS(index+1, i+1)
                
N, M = map(int, input().split())
c = [0] * (N+1)
count = 0

DFS(0, 1)
print(count)

- 상태트리가 여러 가지로 뻗어있는 문제 (DFS 사용)

- 기본 로직은 중복 순열과 비슷하나, start 지점을 같이 넘겨주는 부분이 다르다.

  → for문을 돌 때, start지점부터 시작하도록 한다.

- DFS 다음 index로 넘어갈 때, index는 1 증가 / start지점도 1 증가 시켜준다.

이해를 돕기 위한 상태트리 (start 관련)