[완전탐색][트리] - 중복 수열 구하기(DFS)

문제

• 상태 트리의 경우엔 이진 트리로 선택하거나 선택하지 않거나의 문제로 가지가 뻗어나가는 형태였다.
• 그러나 이 경우엔 여러 가닥의 가지가 뻗는 트리의 형태를 보여준다.

1부터 N까지 번호가 적힌 구슬이 있을 때 중복을 허락하는 조건으로 M개를 뽑아 일렬로 나열하는 방법을 모두 출력하라

문제 풀이

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

if __name__ == "__main__":
    n,m = map(int,input().split())
    res = [0] * m
    cnt = 0
    DFS(0)
    print(cnt)

• 해당 문제는 res라는 리스트에 지금 현재 가지의 값을 n번 돌면서 m개가 됐을 때 출력해주는 형식으로 진행한다.