[파이썬 알고리즘 문제풀이] - Section6 / 완전탐색 (백트랙킹, 상태트리와 CUT EDGE)-DFS(깊이우선탐색)기초 - 6

⚽ 중복순열 구하기

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

import sys
# sys.stdin = open("input.text", "rt")

N, M = map(int, input().split())
data = list(range(N+1))
cnt = 0
res = [0] * M
def DFS(L):
    global cnt
    if L == M: #M개 뽑으면 다 끝남. 종료조건
        for x in res:
            print(x, end = " ")
        cnt += 1
        print()
    else:
        for i in range(1, N+1):
            res[L] = i
            DFS(L+1)
        
    
DFS(0)
print(cnt)  

⚽ 코멘트

DFS라고 판단이 든다면 이 문제처럼 상태트리 가지치기가 여러가지가 나올 수 있다.
해당 경우마다 반복문을 돌면서 어떻게 하면 될 것인지를 고민하자.