1. 탐색(Search)

탐색은 많은 데이터들 가운데 원하는 데이터를 찾아가는 과정이다.

2. DFS

DFS는 깊이 우선 탐색이라 불리며 그래프에서 깊은 부분을 우선적으로 탐색하여 출력하는 알고리즘이다. 마지막 노드까지 내려가면 더 이상 깊이 탐색할 것이 없기에 마지막 노드를 출력하거나 체크한 후에 부모 노드로 다시 올라가고(Backtracking) 다른 자식 노드로 뻗어간다. 그래프는 아래와 같이 노드(Node)와 노드들 사이를 이어주는 간선(Edge)으로 이루어져있다. 그래프는 트리의 형식일 수도 있고 무작위 연결된(양방향 연결 혹은 방향 연결) 형식이 수도 있다.
DFS는 함수가 호출되는 순간부터 순서대로 stack에 다음과 같은 형식으로 쌓인다

def DFS(n):
    if n == 5:
        return
    n += 1
    DFS(n)# <- 
    print(n, end=' ')
DFS(0)
출력:
5 4 3 2 1

1. 먼저 0이 n으로 입력되면 1을 더한 후 재귀로 DFS(1)을 호출한다. 이때 stack에는 [DFS(0)]가 쌓이고 '<-'까지만 진행된다.
2. 다시 n에 1을 더하고 DFS(2)를 호출하면 stack에는 [DFS(0), DFS(1)]이 쌓이고 '<-'까지만 실행이 되고 다시 재귀가 일어난다.
3. 이런 순서로 stack에는 [DFS(0), DFS(1), DFS(2), DFS(3), DFS(4)]가 쌓이고 마지막으로 n이 5가 된 순간 if 조건문에 의해 함수는 종료된다.
4. stack은 후입선출이므로 DFS(4)가 다시 작동을 하는데 '<-'까지만 작동을 했으므로 그 다음 실행문인 print()문을 통해 수가 출력되고 함수가 끝이난다.
5. stack가 빌 때까지 stack에 쌓인 호출문들이 다음 실행문인 print()문을 실행한다.
   이때 보면 0부터 시작하여 1씩 더해가면서 트리를 탐색한다고 보았을 때 가장 나중의 5가 먼저 출력이 되는 것을 볼 수 있듯이, 재귀 함수가 마지막까지 진행되었을 때 break문을 실행하여 stack에 쌓인 재귀 함수들을 종료시켜나간다.
   알고리즘 문제의 형식마다 적용해야 하는 방법은 천차만별이지만 대표적으로 4가지를 염두해두고 DFS를 사용하는데, 순열, 중복순열, 조합, 부분집합을 구하는 방식으로 문제를 풀어나간다. 이번 챕터는 조합이며 각각의 방식에 따라 어떻게 DFS가 이용되는지 알아보자.

3. 조합(Combination)

서로 다른 n개의 원소에서 r개를 중복은 없이 순서 상관없이 나열하는 것을 조합이라고 한다. 예로 1, 2, 3이 있으면 3개 중 2개를 뽑는 방법은 (1, 2), (1, 3), (2, 3) 3개로 기호로는 nCr로 나타낸다.

4.1 문제

n개의 숫자카드가 주어지면 k개를 뽑을 수 있는 경우를 DFS를 이용하여 조합으로 나열하고 몇 가지 경우의 수가 생기는지 출력하시오.
n = [2, 4, 6, 8], k = 2

4.2 풀이

조합은 위 그림과 같이, 반복문을 실행하는 동시에 깊이에 따라서 반복문의 시작 지점도 이동이 되어야 한다. 순열과는 다르게, 조합은 그 순서를 상관하지 않으므로 첫번째 인덱스의 번호의 숫자 2부터 반복문을 시행하였다면 다음은 2가 출력이 되지 않도록 해야하는 것이 포인트다. 그래서 함수를 호출할 2번째 인자는 현재 반복문의 인덱스 다음부터 반복문이 실행될 수 있도록 'idx(현재 할당된 인덱스 번호) + 1'로 DFS를 호출하도록 한다.

def DFS(lv, idx):
    global count
    if lv == k:
        for i in comb:
            print(i, end=' ')
        count += 1
        print()
    else:
        for j in range(idx, len(n)):
            comb[lv] = n[j]# level에 따라 값이 업데이트 하도록 한다.
            DFS(lv + 1, j + 1)# 현재 인덱스가 2번 호출되지 않도록, 다음 인덱스(J + 1)부터 시작하여 할당되도록 한다.
if __name__ == '__main__':
    n = [2, 4, 6, 8]
    k = 2
    comb = [0] * k
    count = 0
    DFS(0, 0)
    print('count: ', count)
출력:
2 4 
2 6 
2 8 
4 6 
4 8 
6 8 
count:  6

순열을 탐색할 때 2번 할당되지 않도록 체크 배열을 가지고 조절을 하였다면, 이번엔 인자를 하나 더 할당함으로써 조절을 한 경우다. '순열은 꼭 체크 배열, 조합은 인자를 추가'가 아닌 문제의 상황에 맞춰 조절할 수 있어야 한다.