DFS(Data Fabric Fundamentals) 및 알고리즘

DFS 기반
깊이 우선 검색(Depth First Search)은 검색 방향의 하나로 넓이 우선 검색(BFS)에 비해 DFS는 각 분기 경로를 더 깊이 파고들 수 없을 정도로 깊이 파고들었다. 이는 트리/그림의 반복, 끼워넣기 관계 처리, 거슬러 올라가기 등에 응용되고 귀속, 스택(stack)으로 DFS 과정을 실현할 수 있다.
 
광도 우선 검색(BFS)에 대한 자세한 내용: 알고리즘과 데이터 구조의 기초-광도 우선 검색(BFS)
반복(Recursion)에 대한 자세한 내용은 알고리즘과 데이터 구조의 기초인 반복(Recursion)
 
나무의 두루
DFS는 주로 두 갈래 트리의 스트리밍에 사용되며, 두 갈래 트리에 대한 자세한 내용은 다음과 같습니다.
알고리즘 및 데이터 구조 베이스 - 두 갈래 찾기 트리(Binary Search Tree)
알고리즘 및 데이터 구조 베이스 - 두 갈래 트리(Binary Tree)
 
관련 LetCode 문제:
559. Maximum Depth of N-ary Tree 문제 해결
897. Increasing Order Search Tree 문제 풀이
872. Leaf-Similar Trees 문제 풀이
108. Convert Sorted Array to Binary Search Tree 문제 풀이
100. Same Tree 문제 풀이
257. Binary Tree Paths 문제 해결
101. Symmetric Tree 문제 해결
110. Balanced Binary Tree 문제 풀이
112. Path Sum 문제 풀이
111. Minimum Depth of Binary Tree 문제 풀이
979. Distribute Coins in Binary Tree 문제 해결
366. Find Leaves of Binary Tree 문제 해결
1123. Lowest Common Ancestor of Deepest Leaves 문제 해결
1110. Delete Nodes And Return Forest 문제 해결
1026. Maximum Difference Between Node and Ancessor 문제 해결
513. Find Bottom Left Tree Value 문제 해결
515. Find Largest Value in Each Tree Row 문제 해결
199. Binary Tree Right Side View 문제 해결
1145. Binary Tree Coloring Game 문제 풀이
337. 하우스 로버 III 문제풀이
863. All Nodes Distance K in Binary Tree 문제 해결
1080. Insufficient Nodes in Root to Leaf Paths 문제 해결
114. Flatten Binary Tree to Linked List 문제 해결
129. Sum Root to Leaf Numbers 문제 해결
971. Flip Binary Tree To Match Preorder Traversal 문제 풀이
105. Construct Binary Tree from Preorder and Inorder Traversal 문제 해결
113. Path Sum II 문제 풀이
109. Convert Sorted List to Binary Search Tree 문제 해결
116. Populating Next Right Pointers in Each Node 문제 해결
430. Flatten a Multilevel Doubly Linked List 문제 풀이
124. Binary Tree Maximum Path Sum 문제 풀이
99. Recover Binary Search Tree 문제 해결
968. Binary Tree Cameras 문제 풀이
 
그림의 두루
트리는 다이어그램의 스트리밍, 시각화 프로세스를 위해 DFS를 사용하는 특수한 그림으로 볼 수 있습니다.
그림에 대한 상세한 설명: 알고리즘과 데이터 구조의 기초 - 그림(Graph)
 
관련 LetCode 문제:
733. Flood Fill 문제 해결
841. Keys and Rooms 문제 해결
695. Max Area of Island 문제 해결
531. Lonely Pixel I 문제 해결
529. Minesweeper 문제 해결
756. Pyramid Transition Matrix 문제 해결
694. Number of Distinct Islands 문제 해결
711. Number of Distinct Islands II 문제 해결
638. Shopping Offers 문제 해결
851. Loud and Rich 문제 해결
802. Find Eventual Safe States 문제 해결
785. Is Graph Bipartite?문제풀이
200. Number of Islands 문제 해결
1034. Coloring A Border 문제 풀이
886. Possible Bipartition 문제 해결
332. Reconstruct Itinerary 문제 해결
827. Making A Large Island 문제 풀이
329. Longest Increasing Path in a Matrix 문제 해결
834. Sum of Distances in Tree 문제 해결
499. The Maze III 문제 풀이
 
네스트된 관계 처리
DFS는 "3[a2[c]"와 같이 중첩 관계가 있는 문제 처리에 사용할 수 있습니다. 예를 들어 LeetCode 문제 394.Decode String:

    // 394. Decode String
    string decode(string s,int& pos){
        string res="";
        int num=0;
        for(;pos){
            if(s[pos]=='['){
                string tmp=decode(s,++pos);
                for(;num>0;num--) res+=tmp;
            }
            else if(s[pos]>='0'&&s[pos]<='9')
                num=num*10+s[pos]-'0';
                else if(s[pos]==']') return res;
                else
                    res+=s[pos];
        }
        return res;
    }

이상은 DFS를 통해 가장 안쪽'[]'에 진입한 후 함수가 되돌아오면서 안쪽 바깥쪽으로 층층이 전개됩니다.
 
관련 LetCode 문제:
394. 디코드 스트링 문제 풀이
690. Employee Importance 문제 풀이
339. Nested List Weight Sum 문제 풀이
364. Nested List Weight Sum II 문제 풀이
1020. Number of Enclaves 문제 해결
439. Ternary Expression Parser 문제 해결
 
DFS 및 역추적
역추적(Backtracking) 알고리즘에서 경로를 선택하고 끝까지 가는 사고방식이 바로 DFS이다.DFS는 역추적 알고리즘의 일부입니다.
소거에 대한 상세한 설명: 알고리즘과 데이터 구조의 기초 - 소거(Backtracking)
 
관련 LetCode 문제:
494. Target Sum 문제 풀이
491. Increasing Subsequences 문제 풀이
473. Matchsticks to Square 문제 풀이
980. Unique Paths III 문제 해결
679.24 게임 문제 풀이
301. Remove Invalid Parentheses 문제 해결
 
DFS 및 Memorization
BFS 프로세스와 마찬가지로 DFS를 적용할 때도 동일한 노드를 반복적으로 액세스할 수 있습니다. 이때 메모라이제이션으로 어떤 노드가 이미 액세스했는지 기록하여 경로가 반복되지 않도록 합니다.
 
관련 LetCode 문제:
851. Loud and Rich 문제 해결
547. Friend Circles 문제 풀이
490. The Maze 문제 풀이
1059. All Paths from Source Lead to Destination 문제 해결
934. Shortest Bridge 문제 해결
489. Robot Room Cleaner 문제 해결
753. Cracking the Safe 문제 해결
749. Contain Virus 문제 해결
514. Freedom Trail 문제 해결
546. Remove Boxes 문제 해결