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

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

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

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

# 상태트리가 여러 가지로 뻗어있는 문제
def DFS(index):
    global count
    
    if index == M:
        for j in range(M):
            print(res[j], end=' ')
        print()
        count += 1
    else:
        for i in range(1, N+1):
            res[index] = i
            DFS(index+1)
        
N, M = map(int, input().split())
res = [0] * M
count = 0

DFS(0)
print(count)

- 상태트리가 여러 가지로 뻗어있는 문제 (DFS 사용)

 

- 0으로 초기화된 res의 역할 : M번 뽑았는지 확인

- if index == M: 마지막 지점에 도달했을 때, res에 담긴 값들을 공백을 두고 출력 / count 1 증가

- else: M번 뽑을 동안 1부터 N까지 for문을 돌면서 해당 값을 res에 담는다.