[인프런] 중복순열 구하기

---

문제설명

1부터 N까지 번호가 적힌 구슬이 있다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력한다.

입력조건

• 첫 줄에 자연수 N(3 <= N <= 10)과 M(2 <= M <= N)이 주어진다.

출력조건

• 첫 줄에 결과를 출력하고 맨 마지막 줄에 총 경우의 수를 출력한다.
• 출력순서는 사전순으로 오름차순으로 출력한다.

사고과정

• 그동안은 상태트리가 두 갈래로만 뻗어갔다. 하지만 이번에는 상태트리가 2개 이상으로 뻗어나가야 한다. 즉 주어진 N에 따라 매번 N가지의 가지가 뻗어나가게 된다. 따라서 DFS 탐색 시 N만큼의 for loop를 추가해주어야 한다.
• 직접 상태트리랑 스택을 연습장에 그려봐야 이해가 훨씬 잘 되었다. DFS를 정복하려면 이렇게 연습장에 그리는 성의(?)정도는 보여야 정복할 수 있다고 한다...하하..열심히 그려야지..

풀이(스스로 못 푼 풀이)

# 이번에는 트리가 여러가지로 갈라짐
n, m = map(int, input().split())
res = [0] * m
cnt = 0

def dfs(idx):
    global cnt
    # 종단
    if idx == m:
        for r in res:
            print(r, end=' ')
        print()
        cnt += 1
    else:
        for i in range(1, n+1):
            res[idx] = i
            dfs(idx+1)

dfs(idx=0)
print(cnt)