깊이 우선 탐색이란
루트 노드(혹은 다른 임의의 노드)를 시작점으로 트리나 그래프에서
한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가 확인 후
다른 루트로 탐색하는 방식을 말한다.일반적으로 재귀호출을 사용하여 구현하지만 단순한 스택 배열로도 구현이
가능하다.주로 BFS(너비 우선 탐색)과 비교된다. 아래 이미지를 참고하면
DFS와 BFS의 차이점을 한눈에 볼 수 있다.
이번 게시글에서는 DFS를 재귀호출을 이용한 문제를 예시로 들어 구현했다.
예시
TreeNode Class
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode() {}
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}먼저 해당 Tree 구조를 만들기 위해 해당 class를 정의하자.
해당 클래스는 현재 노드의 값을 나타내는 val변수와 왼쪽, 오른쪽 노드의
정보를 담고 있는 TreeNode 타입의 left, right 변수를 가지고 있다.
해당 클래스를 이용해서 임의의 트리 구조의 객체를 생성하고 재귀호출을
이용하여 DFS를 구현해본다.
해당 문제는 Reetcode에 있는 129. Sum Root to Leaf Numbers이다.
Main method
public static void main(String[] args) {
// Input: root = [4,9,0,5,1]
TreeNode root =
new TreeNode(4, new TreeNode(9, new TreeNode(5), new TreeNode(1)), new TreeNode (0));
int sum = sumNumbers(root);
System.out.println(sum);
}Main method에선 탐색의 대상이될 TreeNode 인스턴스를 생성하고
최종적인 결과를 받을 sum 변수에 sumNumbers 메서드의 결과를 넣어준다.
sumNumbers
static int sumNumbers(TreeNode root) {
return dfs(root, 0);
}sumNumbers 메서드는 dfs의 결과를 그대로 반환한다.
편의에 따라 만들지 않아도 괜찮지만 나는 dfs 메서드에서 두 결과를 합쳐
반환해주기 위해 만들었다. 아래 dfs 메서드를 보면 이해가 갈거다.
dfs
static int dfs(TreeNode root, int val) {
if(root == null) {
return 0;
}
val = val * 10 + root.val;
if(root.left == null && root.right == null) {
return val;
}
return dfs(root.left, val) + dfs(root.right, val);
}위에서 부터 살펴보면 dfs 메서드는 TreeNode 타입의 root, int 타입의
val을 매개변수로 받고 있다.
호출시 매개변수로 받은 root가 null이라면 더할 숫자가 없기 때문에 0을
반환해준다.
null이 아니라면 val * 10 + root.val을 수행하는데 이것은 예시로 들어보자면
// 현재 val의 상태
val = 4;
4 * 10 = 40;
// 현재 노드의 val
root.val = 9;
(4 * 10) + 9가 된다.
결과는 49이 문제에서는 탐색된 노드의 val을 1차적으로 더하는게 아닌 순서대로 나열하는게 첫 과제이다. 그래서 결과는 49가 맞다.
아래 그림을 보면 현재 구현하는 dfs의 흐름을 이해하기 편할것이다.
탐색한 결과는 아래와 같다.
1. 495
2. 491
3. 40
전부 더하면 1026이 나와야한다.
다시한번 코드의 흐름을 살펴보자.
static int dfs(TreeNode root, int val) {
if(root == null) {
return 0;
}
val = val * 10 + root.val;
if(root.left == null && root.right == null) {
return val;
}
return dfs(root.left, val) + dfs(root.right, val);
}1번
1번째 호출
1. 처음 호출했을때 root의 val은 4, val은 0으로 들어온다.
2. root는 null이 아니기 때문에 조건문을 지나간다.
3. val = val * 10 + root.val이기 때문에 val의 값은 '4'이다.
4. 현재 root의 left, right는 null이 아니기 때문에 조건문을 지나간다.
5. dfs 메서드를 재귀호출한다. 현재 노드의 left와 현재 val(4)를 넘긴다.
2번째 호출
1. 호출했을때 root의 val은 9, val은 4으로 들어온다.
2. root는 null이 아니기 때문에 조건문을 지나간다.
3. val = val * 10 + root.val이기 때문에 val의 값은 '49'이다.
4. 현재 root의 left, right는 null이 아니기 때문에 조건문을 지나간다.
5. dfs 메서드를 재귀호출한다. 현재 노드의 left와 현재 val(49)를 넘긴다.
3번째 호출
1. 호출했을때 root의 val은 5, val은 49으로 들어온다.
2. root는 null이 아니기 때문에 조건문을 지나간다.
3. val = val * 10 + root.val이기 때문에 val의 값은 '495'이다.
4. 현재 root의 left, right는 null이기 때문에 조건에 걸린다.
5. 그대로 val을 반환한다. 반환되는 값은 495이다.
2번
1번째 호출
1. 왼쪽 탐색을 끝낸 후 49에서 dfs(root.right, val)이 호출됨
2. root.right의 val은 '1'이다. val은 49
3. val = val * 10 + root.val이기 때문에 val의 값은 '491'이다.
4. 현재 root의 left, right는 null이기 때문에 조건에 걸린다.
5. 그대로 val을 반환한다.
반환된 값
1. 왼쪽탐색, 495와 491을 더해 반환한다.
3번
1번째 호출
1. 반환된 값 495 + 491이 처음 dfs 호출로 돌아간다.
2. 처음 dfs호출에서도 먼저 수행된건 왼쪽 탐색이다. 이제 우측 탐색 시작
4. root.right의 val은 0이다. val은 4이다.
5. 일단 처음 조건문에서 root는 null이 아니기 때문에 지나간다.
6. val = val * 10 + root.val을 수행한다.
7. root.val은 '0', val은 '4'이기 때문에 val은 40이다.
8. 현재노드는 left, right가 null이다 그대로 val을 반환한다.
반환된 값
1. 왼쪽에서 탐색된 495 + 491 + 40이 더해져 반환된다.
2. sum 변수는 1026을 값으로 가지게 된다.
3. 출력해보면 sum은 1026을 가지고 있다.
그림을 보고 천천히 코드와 함께 흐름을 따라가면서 읽어보자.
