[알고리즘] 중복 순열 구하기(DFS)

(문제) 중복 순열 구하기(DFS)

---

1부터 N까지 번호가 적힌 구슬이 있습니다.

이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

입력설명

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

출력설명

첫 번째 줄에 결과를 출력합니다.

맨 마지막 총 경우의 수를 출력합니다.

출력순서는 사전순으로 오름차순으로 출력합니다.

테스트케이스

입력예제	출력예제
3 2	1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 9
5 3	1 1 1 1 1 2 1 1 3 1 1 4 1 1 5 1 2 1 1 2 2 1 2 3 1 2 4 … 5 5 1 5 5 2 5 5 3 5 5 4 5 5 5 125

---

해결방법

dfs를 이용하여 트리의 형태가 node 3개씩을 갖는 트리라고 생각을 한다.

res 리스트를 n개 만큼 생성하여 0으로 초기화한다.
(res리스트는 중복될 수 값을 넣을 것이다.)

각 node에 들어갈 때마다, 반복문으로 돌린 수열의 값을 dfs를 통해 인덱스 위치를 나타내는 x를 통해서 res 인덱스에 값을 변경시킨다.

---

코드

def dfs(x):
    global count
    # x 인덱스가 m을 가르키는 경우 즉 인덱스 마지막을 넘어서를 가르키는 경우
    # 요소 3개인 인덱스는 인덱스 2가 최대 -> 3일 경우 초과 그때 print
    if x == m:
        for j in range(m):
            print(res[j], end=' ')
        count = count + 1
        print()
    else:
        # dfs를 여러번 반복
        for i in range(1,n+1):
            # res의 인덱스 값 부분을 i로 덮어씌운다
            res[x] = i
            dfs(x+1)

n, m = map(int,input().split())

# 순열
res = [0] * n
count = 0

dfs(0)

print(count)