파이썬 알고리즘-47 (DFS/BFS) 중복순열 구하기

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

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

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

▣ 입력예제 1
3 2

▣ 출력예제 1
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
9

내 코드

상태공간트리가 나온 것을 봐도 어떤 식으로 구현해야 할지 감도 못잡았다.

풀이

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]*n
    cnt=0
    DFS(0)
    print(cnt)

반성점

• DFS에 관한 문제를 수없이 많이 풀었어도 구현을 못함

배운 것

• 카티션 프로덕트(Cartesian Product): 곱집합. 두 집합에서 하나씩 뽑아 만들 수 있는 모든 조합. 중복순열은 동일한 집합이 두 개 있는 것과 같다. 문제는 DFS관련 내용이기에 사용하지는 않았다.
  위 문제를 카티션 프로덕트를 사용해 구하면

from itertools import product

n,m=map(int,input().split())
p=product(range(1,n+1),repeat=m)
p=list(p)
print(p)
print(len(p))