[알고리즘] DFS

DFS를 구현하는 것은 크게 의미가 없는 것 같으므로 간단히 설명하고 넘어가자

하나의 노드에 대해, 해당 노드가 가진 child node를 완전히 탐색하고 넘어가는 것을 DFS이라고 한다

stack을 사용하여 노드의 순회를 컨트롤한다

속도는 느리지만, 저장 공간의 수요가 적고 구현이 간단하다는 장점이 있다.

특히 그래프를 search 할때는 root의 위치에 따라 preorder, inorder, postorder로 나뉜다

 

예시1. 230. Kth Smallest Element in a BST

 

다음과 같은 간단한 예시문제를 보자. 대표적인 그래프인 트리에 대한 문제이다.

트리를 방문하되, 크기순대로 세웠을때 k번째에 있는 노드의 value를 리턴하라는 문제이다.

 

일종의 inorder traversal 문제가 된다. 

노드를 내림차순으로 정렬해야 하기 때문에, left->root->right의 순서대로 노드를 순회하여 답을 구하였다.

 

 

예시2. 199. Binary Tree Right Side View

 

이 문제는 가트리의 right side view만 다시 리턴하라는 문제이다.

얘도 결국에 search문제인데, 결국 모든 노드를 순회하면서 조건에 맞는 처리를 해주는 방식으로 풀어내기 때문이다.

 

조금 더 생각할 부분은 depth에서 right side를 구성하는 노드는 단 한개라는 사실

그리고 right노드가 없다면 left노드가 보인다는 사실 정도다

결국 search의 순서를 recursion으로 풀어낸 것이 특징이다.

 

 

예시3. 98. Validate Binary Search Tree

 

왠지 DFS에서 Tree로 포커스가 어긋난 것 같지만 여기까지 해보자

사실 트리의 node들을 탐색하는 문제들은 결국에 BFS아니면 DFS로 처리하는 문제가 될 것이다.

트리의 노드들이 valid한지 여부를 판단하는 문제

 

역시 재귀를 사용하며 최대,최솟값을 함께 넘긴다

특정 노드를 기준으로 왼쪽은 root의 value가 최대가 되고, 오른쪽은 root의 value가 최소가 될 것이다.

 

 

예시4. 437. Path Sum III 

역시 트리를 탐색하면서 순회한 노드의 합이 주어진 targetSum의 값과 같은 경우의 수를 찾는 문제

 

이 문제는 경우의 수 보다는 recursion의 케이스가 헷갈릴 수 있다는 주의때문에 넣어봤다

DFS는 특정 node를 시작으로 DFS를 진행하며 모든 탐색을 마칠 수 있으나,

문제는 모든 node가 시작 node로 될 수 있다는 것이다

따라서 DFS 뿐 아닌 재귀를 한번 더 추가해주었다.

 

 

예시5 114. Flatten Binary Tree to Linked List

 

.  Flatten Binary Tree to Linked List

이번엔 주어진 트리를 Linked List로 변환하는 문제다

결국이는 preorder순회와 같다. root->left->right순으로 DFS를 진행해주면 된다.

내림차순의 탐색, 즉 깊이 탐색 문제와 동일하기 때문이다

 

DFS 함수는 node와 tail을 갖는데, 항상 특정 node를 기준으로 node의 left는 null이 된다

또한 node.right는 left가 먼저 붙고 right가 붙은 형태로 되어있어 DFS를 이용하여 순서대로 붙여준 것이다.

 

예시6 617. Merge Two Binary Trees

 

traversal에 대한 문제를 하나만 더 풀어보겠다

두개의 트리를 합치는 문제이다.

 

 

root->left->right순서로 순회한다는 점에서 pre-order traversal이라 할 수 있다

기본적으로 트리는 이렇게 재귀를 적극적으로 사용한다

 

 

예시7. 200. Number of Islands

 

트리를 벗어난 문제를 풀어보겠다

이번엔 2차원 adjacent한 1의 덩어리를 찾으라는 문제이다

 

DFS함수에 조건을 넣어 만들었다

1을 만났을때 0으로 노드를 바꾸고, 모든 1마다 카운팅을 하면서 루프를 돌게 만들었다

 

 

예시8. 79. Word Search

 

마지막으로 2차원 배열 문제를 하나 더 풀어보겠다

이번에는 word라는 string이 주어질 때, 이 문자를 연속된 배열의 원소들로 만들수 있는지 여부를 리턴하는 문제이다

 

접근 방식을 먼저 정하는 것이 중요할듯 하다.

내 경우에는, i , j, board, remain을 모두 input으로 받는 dfs로 문제를 풀어보려 한다.

 

실제 루프는 2중으로 돌려주고, dfs에서 문제가 없을때 true를 리턴하도록 한다

이때 dfs 로직은 연속된 문자를 만들 수 있을때까지 진행되어야 한다

 

dfs 로직은 다음과 같다

하나의 단어를 검사할 차례가 되면, 해당 단어를 다시 체크하지 못하도록 -로 바꾸고 remain word를 하나씩 줄여가며 재귀로 비교한다