[Algorithms] 완전탐색(백트랙킹, 상태트리와 CUT EDGE)/깊이우선탐색(DFS) Basic-중복순열 구하기(DFS)

 

 

• 1~N번의 구술을 중복을 허용하여 M번 뽑는 것이므로 이진 트리의 줄기가 N 줄기로 나뉘면 된다
• Level 0 에서 1,2,~N 중에 하나 뽑고, Level 1 에서 1,2,~N 중에 하나 뽑고... Level이 M에 도달하면 결과 print 

import sys
# sys.stdin=open("input", "r")
input=sys.stdin.readline    # 입력양이 많을 때 이 라인을 쓰면 입력 속도가 빨라진다
# s=input().rstrip()        # 위의 라인을 사용하게 되면 문자열을 읽을 때 줄바꿈 기호가 들어오므로 이를 날려야한다
 
def DFS(level):
    global cnt
 
    if level==m:
        cnt+=1
        for i in range(m):
            print(res[i], end=' ')
        print()
    else:
        for i in range(1, n+1):
            res[level]=i
            DFS(level+1)
 
if __name__=='__main__':
 
    n, m = map(int, input().split())
    cnt=0
    res=[0]*m
    DFS(0)
    print(cnt)