[Algorithm] Depth-First Search(DFS)

이전에 BFS(Breadth-First Search)에 대해 공부했었습니다.

오늘은 그 친구격인 Depth-First Search(깊이우선탐색)에 대해서 알아보도록하겠습니다.

마찬가지로 DFS라는 더 많이 불립니다.

 

특징

출처: https://en.wikipedia.org/wiki/Depth-first_search

BFS와 마찬가지로 기본개념은 Tree 구조에서 파생되었습니다.

BFS에 대해 잠깐 복습해보면, BFS의 순회 기준은 노드의 Depth입니다.

순회 기준과 이름이 헷갈릴 수 있지만, BFS는 낮은 Depth를 우선적으로 탐색하기 때문에 기준이 Depth가 됩니다.

출처: https://en.wikipedia.org/wiki/Tree_(data_structure)

Depth: 0 = [2] 
Depth: 1 = [7, 5] 
Depth: 2 = [2, 10, 6, 9] 
Depth: 3 = [5, 11, 4]

2 -> 7 -> 5 -> 2 -> 10 -> 6 -> 9 -> 5 -> 11 -> 4
D:0  D:1       D:2                  D:3
(D = Depth)

 

그렇다면 DFS의 기준은 뭘까요? DFS의 순회 기준은 Child 노드입니다.

BFS에서 활용했던 기준으로 Pre-Order 방식의 DFS로 순회해보겠습니다.

2  : root
|
7  : root의 (Pre-Order 기준) 첫번째 자식 노드
|
2  : 7의 첫번째 자식 노드
|
10 : 7의 두번째 자식 노드
|
6  : 7의 세번째 자식 노드 
|
5  : 6의 첫번째 자식 노드 
|
11 : 6의 두번째 자식 노드 
|
5  : root의 두번째 자식 노드 
|
9  : 5(root의 두번째 자식 노드)의 첫번째 자식 노드 
|
4  : 9의 첫번째 자식 노드

 

이와 같이 순회하기 위해서 주로 재귀와 Stack 자료구조를 활용하게 됩니다.

활용

BFS와 마찬가지로 Backtracking과 Graph 탐색에 활용됩니다.

특정 Graph 노드에서 탐색을 시작했을 때, 연결된 컴포넌트가 무엇인지, 사이클을 갖는 Graph인지 판별할 수 있습니다.

구현(Tree)

BFS 구현 시 사용했던 코드를 다시 사용해봅시다.

class TreeNode {
    var value: Int
    var childNodes: [TreeNode] = []
    
    init(value: Int) {
        self.value = value
    }
    
    func insert(node: TreeNode) {
        childNodes.append(node)
    }
}

let root = TreeNode(value: 2)
var tempNode0 = TreeNode(value: 6)
tempNode0.insert(node: TreeNode(value: 5))
tempNode0.insert(node: TreeNode(value: 11))
var tempNode1 = TreeNode(value: 7)
tempNode1.insert(node: TreeNode(value: 2))
tempNode1.insert(node: TreeNode(value: 10))
tempNode1.insert(node: tempNode0)
root.insert(node: tempNode1)
tempNode0 = TreeNode(value: 9)
tempNode0.insert(node: TreeNode(value: 4))
tempNode1 = TreeNode(value: 5)
tempNode1.insert(node: tempNode0)
root.insert(node: tempNode1)

DFS 순회를 해봅시다. 함수의 재귀 호출과 Stack이 사용됩니다.

var search: [Int] = []
var stack: [TreeNode] = []
func DFS(node: TreeNode) {
    search.append(node.value) // 꺼낸(순회한) 노드 값 추가
    for child in node.childNodes { // 자식 노드 순서대로 순회
        DFS(node: child) // 자식노드에 대해 다시 함수 호출
    }
}

실행해봅시다.

DFS(node: root)
print(search.map(String.init).joined(separator: " -> "))
// 2 -> 7 -> 2 -> 10 -> 6 -> 5 -> 11 -> 5 -> 9 -> 4

정상적으로 작동합니다.

 

예제

BFS에서 풀었던 문제를 DFS로 풀어봅시다.

https://leetcode.com/problems/same-tree/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p?.val != q?.val { return false }
        
        // 왼쪽 Child 노드 우선 탐색
        if p?.left != nil || q?.left != nil {
            if !isSameTree(p?.left, q?.left) { // 재귀 호출
                return false
            }
        }
        
        // 오른쪽 Child 노드 탐색
        if p?.right != nil || q?.right != nil {
            if !isSameTree(p?.right, q?.right) { // 재귀 호출
                return false 
            }
        }
        return true
    }
}

마찬가지로 실제로는 보다 복잡하게 활용되고 재귀 로직의 부하를 줄이기 위해 값을 Caching하기도 합니다.

Conclusion

DFS도 코딩테스트 빈출 유형 중 하나입니다.

재귀 호출 시점과 순회 기준을 잘 파악하는 것이 중요하다고 생각합니다.