[DFS기초] - 중복순열 구하기

 

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:
        cnt+=1
        print(ch)

    else:
        for i in range(1,n+1):
            ch[L]=i
            DFS(L+1)
            
n,m=map(int,input().split())
cnt=0
ch=[0]*m

DFS(0)
print(cnt)

 

아래 그림과 같이 DFS를 입력 받은 숫자의 가지수로 탐색을 진행 하며 체크 리스트에 해당 숫자를 저장

 

정답 코드

import sys
sys.stdin=open("input.txt", "r")
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)

 

오오오 나의 코드와 완전 같다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ공부 열심히한 보람이 있고마잉