[Java 알고리즘] 노드의 최대 깊이, DFS/BFS로 각각 풀어보기 (feat. Stack, Queue, DFS BFS 알고리즘 비교)

다음과 같은 다이어그램을 구현한 아래의 코드를 이용하여 노드 다이어그램의 최대 깊이를 구하는 코드를 작성하시오.

DFS(깊이우선탐색) 과 BFS(너비우선탐색) 탐색방법을 이용하여 각각 작성하시오.

 

TreeNode 클래스

class TreeNode {
        public int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

메인 메소드

public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(9);
        root.left.left = new TreeNode(7);
        root.left.right = new TreeNode(8);
        root.left.left.left = new TreeNode(5);
        root.left.left.left.left = new TreeNode(2);
        root.left.left.right = new TreeNode(6);
        root.right = new TreeNode(11);
        root.right.left = new TreeNode(12);
        root.right.right = new TreeNode(13);

        System.out.println(solutiondfs(root));
        System.out.println(solutionbfs(root));
    }

 

 

---

 

나의 풀이

BFS 버전

public static int solutionbfs(TreeNode root) {
        if(root == null) return 0;
        int count = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i<size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            count++;
        }
        return count;
    }

BFS는 대부분 Queue를 이용하여 작업합니다. 너비우선탐색은 root 부터 Queue에 넣고 while문에 돌립니다. while 내부에서 큐는 채워져야하고 뽑혀야합니다.

root인 10을 빼고 left, right 여부를 탐색한 후 left 와 right를 큐에 넣어줍니다. 이러면 큐 size는 2가되고 count 는 1이됩니다. 

 

이런식으로 7, 8, 12, 13을 Queue에 넣고 count++;

 

그다음 그 자식노드를 Queue에 넣어주고 count를 증가시켜줌에 따라 마지막에 Queue는 Empty true가 되고 while문을 탈출하게 됩니다.

 

따라서 max depth는 5가 출력되게 됩니다.

 

 

DFS 버전

public static int solutiondfs(TreeNode root) {
        if(root == null) return 0;
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> countStack = new Stack<>();
        stack.push(root);
        countStack.push(1);
        
        int max = 0;
        while(!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            int count = countStack.pop();
            max = Math.max(max, count);
            
            if (treeNode.left != null) {
                stack.push(treeNode.left);
                countStack.push(count + 1);
            }
            if (treeNode.right != null) {
                stack.push(treeNode.right);
                countStack.push(count + 1);
            }
        }
        return max;
    }

스택은 방향이 중요합니다. 현재 left 먼저 검사하므로 반대인 right부터 쭉 타고타고 들어가게 됩니다.

stack push 방향

스택은 후입선출이므로 루트의 left 인 9가 들어가게 되고 11이 들어가게 됩니다.

이때 후입선출이므로 11부터 12와 13이 Stack으로 들어가게 됩니다. 

 

12와 13이 들어갔고 나중에 들어간 13부터 검사하는데 자식노드가 없으므로 13에서 pop을 했을 때 count max가 되게 될것입니다. 이런식으로 12에서 pop했을 때 max 함수로 최대값을 검사합니다.

 

결국 빨간색선에 다다를 것이고 count를 pop 했을 때 max 함수에 의해 최댓값이 5로 결정되게 됩니다.

 

---

 

이렇게 BFS와 DFS로 같은 문제를 각각의 방식으로 풀어보았습니다. 이렇게 글을 포스팅함으로써 머리로만 그렸던 알고리즘을 직접 그림으로 그려가면서 이해할 수 있는 시간을 가져서 다행이라고 생각하고 좀더 알고리즘 문제들을 자주자주 접해봐서 대회도 한번 나가보고 싶네요.

 

감사합니다.