Algorithm - 중복순열 구하기(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[중복순열 구하기(DFS)]

 

1부터 N까지 번호가 적힌 구슬이 있다.

이 구슬 중에서 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 자연수 N(3 ≤ N ≤ 10)과 M(2 ≤ M ≤ N)이 주어진다.

 

*출력 설명

첫 번째 줄에 결과를 출력한다.

맨 마지막에는 총 경우의 수를 출력한다.

출력순서는 오름차순 및 사전순으로 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_48.txt', 'rt')

def DFS(L):
    global cnt
    if L == m:
        for j in range(m):
            print(res[j], 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)
    
'''
출력 :
1 1 
1 2 
1 3 
2 1 
2 2 
2 3 
3 1 
3 2 
3 3 
9

'''

 

input_48.txt(입력)

3 2

 

 

중요내용

1. 리스트 res는 중복수열의 결과를 저장하기 위한 용도로 선언된 리스트이다.
2. 변수 cnt는 총 경우의 수를 표기하는 변수이다.
3. 변수 L은 리스트의 인덱스 번호로써 중복수열의 자리수를 의미한다.
4. 즉, n의 입력 값이 2이면 중복수열의 자리수도 두 자리이므로 리스트의 인덱스 번호인 L은 0부터 1까지 필요하다.
5. 기본적으로 스택 자료구조를 활용한 재귀함수의 매커니즘으로 문제를 해결한 답안이다.
6. DFS() 함수 내에서 반드시 global cnt를 작성해줘야만 변수 cnt가 전역변수가 되어 에러가 발생하지 않는다. (해당 함수 내에서 변수 cnt를 정의한 식이 존재하기 때문 : " cnt += 1 ")