Depth/Breadth First Search

Brute Force Search의 대표적인 알고리즘인 DFS 와 BFS 에 대해 알아보자.

1. Brute Force Search

효율적으로 풀 수 있도록 계획을 세워 푸는 것이 아닌 가능한 경우의 수를 모두 탐색하는 방법이다. 어떻게든 정답을 얻어낼 수 있지만 데이터 수가 증가할수록 실행 시간이 증가한다.

자료 구조에 따라 사용되는 Brute Force Search 방법은 다음과 같다.

• 선형 자료구조(배열, 스택, 큐): 순차 탐색
• 비선형 자료구조(그래프, 트리): DFS, BFS

Brute Force 는 얼마나 비효율적일까?

Brute Force 로 작성한 코드의 시간 복잡도를 확인해보고, 다른 방법으로 최적화 해보자! 예시로 LeetCode 의 1번 문제인 Two Sum 을 살펴본다.

https://leetcode.com/problems/two-sum/

문제를 간단하게 요약하면 다음과 같다.

• 정수 배열 nums 와 정수 target 이 주어짐
• 더했을 때 target이 되는 (nums 내의) 서로 다른 요소의 인덱스를 반환

Brute Force 로 풀어보면 다음과 같다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

이 코드는 간단해보이지만 시간 복잡도가 O(N²)이므로 데이터가 늘어날수록 실행 시간이 많이 증가할 것이다.

사실 이 문제에서는 이중 루프를 사용할 필요가 없다. 왜냐하면 배열의 원소 a 가 주어졌을 때, target-a 값이 딕셔너리의 키에 존재하는지 확인하고 존재한다면 a 와 target-a 의 인덱스를 반환하면 되기 때문이다. (target = a + (target-a))

여기에서 지난 글에서 설명했던 해시 테이블 자료구조를 사용할 수 있다. 파이썬의 딕셔너리를 활용하여 구현하는 순서는 다음과 같다.

1. nums[i] 를 키로, 인덱스 i 를 값으로 하는 딕셔너리 d 를 생성
2. target 에서 배열의 원소 num[j] 를 뺀 값인 search 가 d에 존재하는지 확인
   -> 존재한다면 j 와 d[search] 를 반환 (d[search] 는 배에서 값으로 search 를 가지는 요소의 인덱스를 의미)
3. 2번을 배열의 크기만큼 반복

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {nums[i]: i for i in range(len(nums))}
        for j in range(len(nums)):
            search = target - nums[j]
            if search in d:
                if d[search] == j:
                    continue
                return [j, d[search]]

위처럼 딕셔너리를 활용하여 최적화한 코드는 배열의 개수만큼만 반복하면 되기 때문에 시간 복잡도는 O(N) 이 된다. Brute Force 방식으로 문제를 풀면 시간 복잡도를 만족하지 못해 알고리즘 테스트에 통과하지 못할 수 있다. 따라서 문제에 적합한 자료구조와 알고리즘을 선정하여 해결해야 한다.

2. Graph & Tree

DFS 와 BFS 는 그래프와 트리의 특성에 따라 구현하는 방법에 차이가 있다. 따라서 그래프와 트리의 차이를 인지하고 있는 것이 중요하다.

그래프

• 노드(정점 이라고도 함)와 노드를 연결하는 간선으로 이루어진 자료 구조
• 방향이 있을 수도 있고, 없을 수도 있음
• Cycle(순환)이 있을 수도 있고, 없을 수도 있음 (순환이란 출발한 노드에서 시작해 출발한 노드로 돌아오는 경로를 말한다.)
• 사이클이 있을 수 있기 때문에 순회할 때는 방문한 노드를 기록하여 중복으로 방문하지 않도록 해야 한다.

트리

• 그래프의 일종이며, 노드와 간선으로 이루어진 자료 구조
• 루트 노드(최상단 노드)가 존재
• 부모-자식 노드가 간선으로 연결되며 레벨이 존재하는 계층적 구조
• 노드는 왼쪽 자식 노드와 오른쪽 자식 노드를 가질 수 있음

3. DFS(Depth-First Search, 깊이 우선 탐색)

깊이 우선 탐색이란 지정된 노드에서 시작하여 해당 분기를 완벽하게 탐색 후 다음 분기를 탐색하는 방법이다. DFS 는 스택이나 재귀 함수로 구현한다.

트리에서의 DFS

노드 자신을 언제 방문하는지에 따라 세 가지로 구분한다.

• pre-order(전위): 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리
• in-order(중위): 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리
• post-order(후위): 왼쪽 서브트리 -> 오른쪽 서브트리 -> 노드

이진 트리의 전위 순회의 과정은 다음과 같다.

1. 시작 노드를 방문
2. 방문한 노드의 왼쪽 노드를 방문하고 오른쪽 노드가 있다면 스택에 추가(push) 하는 과정을 왼쪽 노드가 존재하지 않을 때까지 반복
3. 가장 마지막에 들어온 노드를 제거 후 방문 (pop)
4. 2와 3을 스택이 빌 때까지 반복

그래프에서의 DFS

그래프의 DFS 의 과정은 다음과 같다.

1. 시작 노드를 스택에 추가(push)하고 제거(pop)한 후 방문
2. 방문한 노드의 방문하지 않은 이웃 노드들을 스택에 추가(push)
3. 추가된 노드 중 가장 마지막에 들어온 노드를 제거(pop)한 후 방문
4. 2와 3을 스택이 빌 때까지 반복하게 됨

4. BFS(Breadth-First Search, 너비 우선 탐색)

너비 우선 탐색이란 같은 수준의 노드를 모두 탐색한 후 다음 수준의 노드를 탐색하는 방법이다. BFS 는 큐로 구현할 수 있다.

트리에서의 BFS

트리 관점에서 BFS 는 낮은 수준부터 시작하여 한 수준의 노드들을 부모 노드의 방문 순서에 따라 방문한다.

이진 트리의 BFS 의 과정은 다음과 같다.

1. 시작 노드를 큐에 추가(enqueue) 하고 제거(dequeue)한 후 방문
2. 방문한 노드에 왼쪽, 오른쪽 자식이 있다면 순서대로 큐에 추가(enqueue)
3. 큐의 가장 앞에 있는 노드를 제거(dequeue) 후 방문
4. 2와 3을 큐가 빌 때까지 반복하게 됨

그래프에서의 BFS

그래프 관점에서의 BFS 는 한 노드의 이웃 노드를 모두 방문하고, 또 방문한 노드의 이웃 노드를 방문한다.

1. 시작 노드를 큐에 추가(enqueue) 하고 제거(dequeue)한 후 방문
2. 방문한 노드의 방문하지 않은 이웃 노드를 큐에 추가(enqueue)
3. 큐의 가장 앞에 있는 노드를 제거(dequeue) 후 방문
4. 2와 3을 큐가 빌 때까지 반복하게 됨