학교에서 자료구조를 배울 때 나는 코딩을 하나도 할 줄 몰랐고 꾸역꾸역 C+만 받고 끝내서 ps를 하려고 보니 DFS, BFS, 트리, 그래프 뭐 이런 거 아무 것도 모르는 상태였다. 전공생이 백트랙킹을 이제와서 블로그에 글 적으면서 공부하는 게 웃기긴 한데, 그래도 어쩌겠나 이렇게라도 기록하면서 공부하는 거지.
거두절미하고 블로그에 처음 남기는 알고리즘은 백트랙킹(Backtracking)이 되겠다. 우선 탐색에 대한 이해가 필요하니, 탐색 중 깊이 우선 탐색(DFS, Depth-First Search)에 대해서 알아보겠다.

DFS

DFS(Depth-First Search)
깊이 우선 탐색, 루트 노드에서 시작하여 다음 branch로 넘어가기 전 헤당 branch를 완벽히 탐색하는 방법으로, 가능한 모든 경우의 수를 다 알아본다. 스택, 재귀를 사용한다.
-동작 방식-
1. 루트 노드(탐색 시작 노드)를 스택에 삽입, 방문처리한다.
2. 이후 스택의 최상단 노드의 주변 노드 중 방문하지 않은 노드가 있다면 해당 노드를 스택에 삽입, 방문 처리한다. 만약 스택의 최상단 노드의 주변 노드 중 방문하지 않은 노드가 없다면 스택의 최상단 노드를 스택에서 빼내준다.
3. 방문하지 않은 노드가 없을 때까지 2의 과정을 반복한다.

간단한 예를 들어보겠다.

이런 트리 구조가 있다고 할 때 DFS의 탐색을 살펴보자. 탐색 기준은 번호가 낮은 인접 노드부터이다. 우선 루트 노드인 1을 스택에 넣어준다.

그 다음, 인접 노드 중 번호가 낮은 노드인 2를 방문, 스택에 삽입해준다.

이제 2의 인접 노드 중 작은 수인 4를 방문, 스택에 삽입한다.

4의 인접 노드는 2밖에 없는데 2는 스택에 존재하므로, 방문한 노드이다. 이 상황이 위에서 언급한 DFS의 동작방식 2에서의 인접 노드 중 방문하지 않은 노드가 없는 경우이다. 그런 상황에서의 조치가 바로 스택에서 빼주는 것이었다. 4를 스택에서 빼주자.

2의 인접 노드 중 4는 아까 방문했으므로, 5를 방문해주고 스택에 넣어주자.

5도 4와 마찬가지로 인접한 노드 중 방문하지 않은 노드가 없는 노드이다. 5도 마찬가지로 스택에서 빼주자.

그럼 스택에는 1, 2가 남아있다. 스택의 최상단 노드인 2의 인접 노드는 4와 5인데 모두 방문했던 노드이다. 이제 2를 스택에서 빼주자.

이제 스택의 최상단에는 1이 있다. 1의 인접 노드 중 3은 방문하지 않은 노드니 3을 방문, 스택에 삽입해주자.

3의 인접 노드는 1, 6이다. 방문하지 않은 노드는 6이므로 6을 방문, 스택에 삽입하자.

이렇게 함으로써 모든 노드를 방문했다. 스택에 삽입된 순서를 살펴보면 1->2->4->5->3->6의 순이다. 이 순서로 모든 노드를 방문, 탐색하는 것이 DFS의 동작 과정이다.

DFS의 경우 모든 노드를 방문하기 위한 방법이라고 볼 수 있다. 하지만 말 그대로 모든 경우의 수를 다 알아보는 방법이므로, 문제의 답을 구할 때 불필요한 경로까지 다 조사할 수도 있다. 경우의 수가 작다면 괜찮겠지만, 경우의 수가 많은 문제에 대해 DFS로 풀이를 시도했다가는 시간, 공간적 문제가 발생할 것이다. 이러한 문제를 해결해줄 수 있는, 자세히 말하면 불필요한 것 같은 경로를 마주쳤을 때의 경로를 차단해주는 알고리즘이 바로 백트랙킹 알고리즘이다.

Backtracking

Backtracking
가능한 모든 경우의 수를 따져보지만, 해가 되기 힘들다고 판단되면 즉시 해당 경로를 차단하며 해를 찾아가는 알고리즘이다. 백트랙킹을 잘 구현하기 위해서는 경로가 유망한지 여부(promising), 가지치기(prunning)가 중요하다.

• 특정한 조건을 만족하는 경우(promising)만 살펴보는 것.
• 답이 promising하지 않으면 prunning을 해주는 것이 중요.
• 주로 DFS를 통한 탐색 중 prunning의 조건을 걸어 해당 조건을 마주하면 탐색 중지, 그 이전으로 돌아가 다시 다른 경로를 탐색하는 식으로의 구현.

대표적인 예제로 백준에 올라와 있는 N과 M문제가 있다.

이렇게 수열을 구하는데, 오름차순인 수열만을 구해야하는 경우가 바로 백트랙킹이 필요한 경우이다. 그냥 수열만 구한다면 DFS로 해결이 가능할 것이다. 그렇지만 여기서 오름차순이라는 조건이 들어가므로 prunning을 해줘야하는 것이다. 그럼 N은 4, M은 2인 경우에 대해서 그림으로 이해해보자.

먼저, 1이 루트노드일 때다. 이 때는 뒤의 2, 3, 4가 모두 1보다 큰 수이므로 어떤 수가 스택에 들어가더라도 오름차순이라는 조건이 충족된다. 그러므로 2, 3, 4를 모두 방문 해주면 되는 것이다. => (1, 2), (1, 3), (1, 4)

문제는 이제부터 발생한다. 2가 루트노드일 경우 방문 가능한 인접 노드는 1, 3, 4이다. 이때 1을 방문한다면 문제의 조건 중 오름차순이라는 조건을 충족하지 못하므로, 1은 방문하지 않아야한다. 3과 4의 경우는 문제의 조건을 충족하므로 모두 방문해주면 된다. => (2, 3), (2, 4)

3이 루트노드인 경우, 방문 가능한 노드는 4가 되겠다. => (3, 4)

4가 루트노드라면 어떨까? 방문 가능한 노드가 존재하지 않는다. 따라서 답은 (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)가 된다.

이제 위의 상황들에서 가지를 치는 경우를 일반식으로 나타내보자. 방문하는 노드는 스택에 삽입해야한다. 스택(stack)에 존재하는 숫자(num)는 이미 방문한 노드이므로, 이를 따져서 넣어줘야한다(if num not in stack). 여기까지는 DFS에서 구현하는 범위이다. 이제 prunning을 해보자. 오름차순이라는 조건이 있으므로 삽입하기 전 스택의 최상단 값(stack[-1])과 비교를 해서 더 큰 값인지 따져봐야한다(if num > stack[-1]). 이를 정리하면

if num not in stack and num > stack[-1]:

와 같은 조건이 탄생하게 된다. 이를 통해 탐색을 하던 중 조건에 부합하지 않는 경로라고 판단되면 탐색을 멈출 수 있는 것이다. 아래는 오름차순이 조건인 N과 M문제의 전체 코드이다. 스택과 재귀, 위에 있는 prunning의 조건을 이용했다.

def backTracking(N: int, M: int, permutation: list) -> None:
    if len(permutation) == M:
        print(" ".join(map(str, permutation)))
        return
    else:
        for i in range(1, N+1):
            if len(permutation) == 0:	# 스택이 비어있을 경우는 최상단 값이 없음.
                permutation.append(i)
                backTracking(N, M, permutation)
                permutation.pop()
            else:	# 스택이 비어있지 않을 때, 최상단 값과 비교.
                if i not in permutation and i > permutation[-1]:
                    permutation.append(i)
                    backTracking(N, M, permutation)
                    permutation.pop()
            

def main():
    N, M = map(int, input().split())
    backTracking(N, M, permutation=[])


if __name__ == "__main__":
    main()

이제 슬슬 백준 풀이 때 자료구조나 알고리즘을 알아야 문제가 풀리는 구간이 온 것 같다. 수학적인 개념을 이용하는 것보다는 자료구조, 알고리즘이 공부를 통해 커버가 가능한 부분인 것 같으니 이 기회에 대학 때 그냥 보내버렸던 것들을 확실히 공부해야겠다.