트리 - 깊이 우선 탐색 알고리즘 (DFS)

깊이 우선 탐색 알고리즘(DFS, Depth First Search)

 

트리를 조회할 때, 깊이를 기반하여 우선적으로 조회한다.

하나의 노드에는 여러 개의 노드가 연결되어 있는데, 특정 노드의 한쪽 방향의 끝까지 먼저 검색한 후 다른 방향의 노드를 검사한다.

 

출처 : https://www.freelancinggig.com/blog/2019/02/06/what-is-the-difference-between-bfs-and-dfs-algorithms/

구현은 Recursive Call 혹은 Stack을 사용한다.

 

위 그림에서 0번 노드시작으로, 왼쪽 노드부터 내려가면서

1. 자신 검사

2. 왼쪽 노드 검사

3. 오른쪽 노드 검사

를 반복하게 된다.

 

이 때, 왼쪽 또는 오른쪽의 서브노드 검사 중 서브노드의 왼쪽, 오른쪽 서브노드가 또 있으면 위 과정을 계속해서 반복하게 된다.

 

트리는 배열로도 표현할 수 있지만, LinkedList로 표현하는 것이 일반적이다.

각 노드는 left, right라는 서브 노드에 대한 레퍼런스를 가지고 있다.

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

따라서 이 left, right 노드를 따라서 검색하다보면, 자연스럽게 트리 구조 상 깊이를 먼저 탐색하게 된다.

 

이러한 것을 DFS, 깊이 탐색 우선 알고리즘이라고 한다.

 

위 트리를 구성하는 소스코드는 다음과 같다.

TreeNode root = new TreeNode(0);
TreeNode left = new TreeNode(1);
TreeNode right = new TreeNode(2);
TreeNode leftleft = new TreeNode(3);
TreeNode leftright = new TreeNode(4);
TreeNode rightleft = new TreeNode(5);
TreeNode rightright = new TreeNode(6);
root.left = left;
root.right = right;
left.left = leftleft;
left.right = leftright;
right.left = rightleft;
right.right = rightright;

 

DFS 함수를 소스코드로 표현하면 다음과 같다.

 

// Recursive Call을 활용한 DFS
public void dfsSearch(TreeNode root) {
    // null이 나올 경우 탐색 종료
    if (root == null) {
        return;
    }

    // 현재 노드의 검사를 먼저 검사
    System.out.print(root.val);
    
    // 왼쪽 노드가 존재한다면 왼쪽 노드를 검사
    if (root.left  != null) dfsSearch(root.left);
    
    // 오른쪽 노드가 존재한다면 오른쪽 노드를 검사
    if (root.right != null) dfsSearch(root.right);
}

 

전체 소스코드는 다음과 같다.

/**
 * 깊이 우선 순회 DFS (Depth First Search)
 */
public class DFS {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode left = new TreeNode(1);
        TreeNode right = new TreeNode(2);
        TreeNode leftleft = new TreeNode(3);
        TreeNode leftright = new TreeNode(4);
        TreeNode rightleft = new TreeNode(5);
        TreeNode rightright = new TreeNode(6);
        root.left = left;
        root.right = right;
        left.left = leftleft;
        left.right = leftright;
        right.left = rightleft;
        right.right = rightright;

        dfsSearch(root);
    }

    // Recursive Call을 활용한 DFS
    public static void dfsSearch(TreeNode currentNode) {
        if (currentNode == null) {
            return;
        }

        System.out.print(currentNode.val);
        if (currentNode.left  != null) dfsSearch(currentNode.left);
        if (currentNode.right != null) dfsSearch(currentNode.right);
    }
}

 

결과는 다음과 같다.

 

대표적인 문제

LeetCode - 100. Same Tree

LeetCdoe - 104. Maximum Depth of Binary Tree