오늘은 DFS를 이용하여 조합의 경우의 수를 출력하고 가짓수도 출력하는 코드를 작성해 봅시다.
조합(Combination) 이란?
고등학교 수학시간에 순열과 조합을 배웠죠.
순서를 고려하고, n개 중 r개를 중복 없이/있이 뽑는 순열
순서를 고려하지 않고, n개 중 r개를 중복 없이/있이 뽑는 조합
그 중 조합 은 순서를 고려하지 않고 n개 중 r개를 중복 허용하지 않고 뽑는 방법 입니다.
접근 방법
A={1,2,3,4} 에서 숫자 2개를 뽑아 조합을 만든다고 가정합시다.
조합으로 만들면 결과는
1 2
1 3
1 4
2 3
2 4
3 4
총 6개가 나옵니다.
이걸 어떻게 만들까요?
만약 원소 1이 뽑혔다면, 나머지 한 자리는 2 or 3 or 4 가 되겠죠?
그 후
만약 원소 2가 뽑혔다면, 나머지 한 자리는 3 or 4 가 되겠죠?
그 후
만약 원소 3이 뽑혔다면, 나머지 한 자리는 4가 됩니다.
A라는 배열에서 i번째 원소가 뽑히면 다음에 뽑힐 수는 i+1번째 원소부터 후보가 될 수 있습니다.
즉, i번째 원소가 뽑힐 수 있는 모든 경우의 수를 구하고, i+1번째 원소가 뽑힐 수 있는 모든 경우의 수를 구할 땐 i+2 번째 원소부터 후보가 될 수 있다는 거죠.
이를 그림으로 그리면 다음과 같습니다.
D(a,b) 에서
a : DFS의 깊이(level)이자 a개 원소를 뽑았음을 나타냅니다. 또한, DFS함수가 끝나는 시점을 지정하기 위해 사용됩니다.
b : b 번째 원소부터 후보가 되어 뽑힐 수 있음을 나타냅니다.
앞서 말한 접근 방법과 그림을 토대로 코드를 작성하면 아래와 같습니다.
def DFS(L, s):
global cnt
if L==m: #m개 원소를 다 뽑으면 멈춤
for i in range(m):
print(res[i], end=' ')
print()
cnt+=1
else:
for i in range(s, n+1): #숫자 s부터 후보가 되어 뽑힐 수 있다.
res[L]=i #level이 곧 원소를 뽑은 횟수
DFS(L+1, i+1) #뽑힌 숫자 다음부터 다시 후보가 되어 뽑힐 수 있다.
n, m=map(int, input().split())
res=[0]*(n+1) #만들어진 조합 배열을 저장하는 공간
cnt=0
DFS(0, 1) # lvl 0 부터 시작, 첫번째 원소부터 후보가 되어 뽑힐 수 있다.
print(cnt)오늘의 게시글 끝!
