파이썬 알고리즘-51 (DFS/BFS) 조합 구하기

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

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

▣ 출력설명
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.

▣ 입력예제 1
4 2

▣ 출력예제 1
1 2
1 3
1 4
2 3
2 4
3 4
6

내 코드

import sys
sys.stdin=open("in2.txt", "r")

def dfs(v):
    global cnt
    if v>m:
        cnt+=1
        for j in range(len(ch)):
            if ch[j]==1:
                print(j, end=' ')
        print()
    else:
        for i in range(v,n+1):
            if ch[i]==0:
                ch[i]=1
                dfs(v+1)
                ch[i]=0         

n,m=map(int,input().split())
cnt=0
ch=[0]*(n+1)
dfs(1)
print(cnt)

순열처럼 풀어서 답이 안나옴.

풀이

def DFS(L, s):
    global cnt
    if L==m:
        for i in range(m):
            print(res[i], end=' ')
        print()
        cnt+=1
    else:
        for i in range(s, n+1):
            res[L]=i
            # s(시작점)가 아닌 i(뻗어나가는 가지)에 +1
            DFS(L+1, i+1)
           

n, m=map(int, input().split())
res=[0]*(n+1)
cnt=0
DFS(0, 1)
print(cnt)

반성점

• 조금만 문제가 바뀌어도 헤맨다.

배운 것

• 순열과는 상태공간트리가 약간 다르다. 순열은 순서가 다르면 다른 것으로 취급하지만 조합은 순서는 상관 없다. 그렇기 때문에 순열은 반복문을 항상 처음 숫자부터 시작해도 되지만, 조합은 다음 레벨에서는 +1부터 시작한다.