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

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

---

DFS - 순열 구하기

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

---

문제

10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

---

입력

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N)이 주어집니다.
두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다.

출력

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

---

입력 예제

3 2

출력 예제

12
13
21
23
31
32

---

코드

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

def solution(n, m):
    ch = [0] * (n+1)
    DFS(0, n, m, ch)
                                       
solution(3, 2)

---

풀이

이 문제는 중복 순열 구하기 문제와 매우 흡사하다.

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