코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.

• IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
• 상세 설명 - 수원대학교(대학일자리 플러스센터)

---

DFS - 중복 순열 구하기

앞서 공부한 DFS(깊이 우선 탐색)을 사용해 중복 순열 구하기 문제를 풀어보겠다.

---

문제

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

---

입력

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

출력

첫 번째 줄에 결과를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.

---

입력 예제

3 2

출력 예제

11
12
13
21
22
23
31
32
33

---

코드

nums = []
def DFS(L, n, m):
    if L == m:
        for num in nums:
            print(num, end= ' ')
        print()
    else:
        for i in range(1, n+1):
            nums.append(i)
            DFS(L+1, n, m)
            nums.pop()

def solution(n, m):         
    DFS(0, n, m)
                 
solution(3, 2)

    

---

풀이

• 먼저 루트 노트(0)에서 DFS를 호출하면 먼저 현재 원소의 개수(L)가 m과 동일하냐 묻는다.
  • 동일한 경우 : 중복을 허용하는 하나의 순열이 만들어진 것이므로 nums의 원소들을 출력한다.
  • 동일하지 않는 경우 : 1부터 n만큼 자식 노드를 만든다.
    만약 자식 노드가 i가 만들어졌다면 순열 nums에 i를 넣는다.
    그 후, 자식 노드 i를 기준으로 또 탐색하기 위해 DFS(L+1)를 호출한다. -> 레벨이 올라간다는 건 그 노드의 자식 노드를 탐색한다는 것을 의미
    이렇게 nums에 m개의 숫자가 담기게 되면 L == m을 또 만족하므로 출력한다.
    이렇게 반복하다가 중복을 허용하며 m개로 나올 수 있는 모든 순열이 출력하면 탐색을 종료한다.