중복순열 구하기(DFS)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/Wa5t

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

#강의 풀이
def DFS(L):
    global res, cnt
    if L == m:
        for i in res:
            print(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] * m
    cnt = 0
    DFS(0)
    print(cnt)

res 는 중복순열을 저장하는 배열

cnt는 중복순열의 개수를 저장하는 변수

 

1부터 숫자가 시작하기때문에

for 문을 1부터 n+1의 범위로 하여

res 배열에 추가한다.

 

DFS를 진행해 L = level 이 n에 도착하면 출력한다.