들어가기에 앞서
참고한 자료를 바탕으로 비전문가가 정리한 글이므로 오류가 있을 수 있습니다.
오류에 대한 피드백은 언제든지 환영합니다. 부디 댓글로 알려주시길 바랍니다. 감사합니다.
Depth First Search
DFS(깊이 우선 탐색)는 그래프에서 노드를 탐색하는 알고리즘 중 하나입니다. 이 알고리즘은 가능한 한 깊이 있게 그래프를 탐색하며, 더 이상 진행할 수 없을 때 되돌아가(백트레킹) 다른 경로를 탐색합니다.
예를 들어, 미로 탐색에서 한 방향으로 계속 진행하다가 막다른 길에 도착하면 다시 되돌아가서 다른 길을 찾아 나서는게 DFS의 작동 방식과 유사합니다.
DFS는 스택(Stack)이나 재귀(recursion)를 사용하여 구현할 수 있습니다. 스택을 사용하는 경우에는 방문한 노드를 스택에 저장하고, 재귀를 사용하는 경우에는 해당 노드를 방문하고 인접한 노드를 재귀적으로 방문합니다.
DFS는 주로 그래프 탐색, 미로 찾기, 그래프의 연결 여부 확인, 위상 정렬 등의 문제에서 활용됩니다.
문제 풀어 보기
이제 문제를 풀면서 배운 개념을 활용해보겠습니다. 아래 문제는 leetcode의 988번 문제 Smallest String Starting From Leaf 입니다. 트리의 리프 노드에서부터 출발하여 루트노드로 도착하는 문자열 구성 중 사전 순으로 가장 작은 문자열을 반환해야하는 문제입니다.
각 노드의 값은 a~z 알파벳을 나타내는 0~25의 수 중 하나로 되어있습니다. 입력값은 루트 노드가 주어집니다.
Smallest String Starting From Leaf
Example 1:
Input: root = [0,1,2,3,4,3,4]
Output: "dba"
Plain Text
복사
Example 2:
Input: root = [25,1,3,1,3,0,2]
Output: "adz"
Plain Text
복사
Example 3:
Input: root = [2,2,1,null,1,0,null,0]
Output: "abc"
Plain Text
복사
풀이
저는 Javascript로 해당 문제를 풀었습니다.
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {string}
*/
var smallestFromLeaf = function(root) {
return dfs(root, "");
function dfs(node, currentPath) {
if (!node) return "감시값"
const newPath = String.fromCharCode(97 + node.val) + currentPath
if (!node.left && !node.right) return newPath
const leftPath = dfs(node.left, newPath)
const rightPath = dfs(node.right, newPath)
if (leftPath < rightPath)
return leftPath
else
return rightPath
}
}
TypeScript
복사
구현 자체는 매우 간단합니다. 앞서 말씀드렸다시피 DFS는 주로 스택이나 재귀로 구현합니다. 위 코드는 재귀 호출로 구현한 경우로써, 아래와 같은 순서에 따라 최단 경로를 반환합니다.
1.
현재 노드에서 시작하여 리프까지의 경로를 생성
2.
현재 노드에서부터 리프까지의 경로를 생성할 때, 현재 노드의 값은 해당 문자열의 가장 앞에 추가
3.
현재 노드가 리프인 경우에는 경로를 완성하고 반환
4.
현재 노드가 리프가 아닌 경우에는 왼쪽과 오른쪽 서브트리에 대해 재귀적으로 dfs 함수를 호출
5.
최종적으로 왼쪽 서브트리와 오른쪽 서브트리에서 얻은 경로 중에서 더 작은 경로를 선택하여 반환
재귀가 잘 안 와닿을 수 있지만 차근차근 단계에 따라 생각해보시면 감을 잡을 수 있다고 생각합니다.