1. Subject : dfs

1. What I learn?

깊이 우선 탐색!

나는 지금까지 그래프에서 BFS와 DFS를 사용하는 방법만 알았었는데 이번에는 그래프가 아닌 노드를 활용해서 DFS를 사용하는 방법을 알게되었다.

DFS의 기본적인 원리는 알고있었다. 노드로 어떻게 사용하는지 지금부터 코딩테스트 문제를 통해서 알아보자

2. What I did?

DFS코드이다.

DFS는 Stack이나 재귀함수로 구현할 수 있다.

여기서는 재귀함수를 통해서 구현했다. DFS는 깊이를 우선으로 탐색하기 때문에 깊은 곳?까지 들어가는 값을 구할 때 빨리 구할 수 있다.

또 다른 문제!

TreeNode가 어떻게 구현되어 있는지 알려주는 주석이다.

left, right를 통해서 갈림길?에 갈 수 있고 val을 통해서 Node의 값에 접근할 수 있다.

class Solution{
   int sum=0;

private void preOrder(TreeNode root, int low, int high){
    if(root!= null){
        if(root.val >= low && root.val <=high){
            sum += root.val;
        }
        preOrder(root.left, low, high);
        preOrder(root.right, low, high);
    }

}
   
    public int rangeSumBST(TreeNode root, int low, int high) {
        
        preOrder(root, low, high);
        return sum;
    }
}

root가 null이 아닌경우(TreeNode가 주어진 경우… 끊긴 경우에는 검사하지 않는다.)

node의 value값이 low보다 크고 high보다 작은지 검사한다.(문제에서 주어진 정답의 조건)

값이 같으면 sum에 값을 더한다.

후에 left ,right 노드를 검사해준다. 이런 방식으로 가장 깊은 곳 까지 도달한다.

2. Review

그래프를 활용한 DFS는 풀어 본 적은 없지만 BFS와 stack, Queue에 저장하는 차이가 있었다. BFS로 그래프로만 풀어봤었는데 오늘 같은 문제도 풀어봐야겠따

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL