[Algorithm] DFS 원리

이번 장에서는 DFS 알고리즘을 적용할 때 JVM의 Stack과 Frame이 어떤 식으로 변경되는지 알아본다.
Stack과 Frame에 대한 정의는 오라클 공식 문서 (링크)를 확인하거나 필자가 정리한 글 (링크)에서 확인한다.

---

아래의 그림과 같은 트리를 DFS로 탐색해보도록 한다.

트리를 탐색하는 코드를 작성하면 아래의 이미지와 같이 작성이 된다.
각 노드를 나타내는 Node 클래스는 숫자를 저장할 data 값과 왼쪽 자식 Node, 오른쪽 자식 Node를 가지고 있다.
main() 메서드에서는 탐색해야하는 트리를 생성하고 있으며 dfs 메서드에서는 main()에서 생성한 트리를 탐색하고 있다.

우리가 주의깊게 확인해야하는 부분은 dfs메서드다.
한줄한줄 진행될 때 Stack의 변화를 살펴보도록 한다.

main 메서드에서 root 노드를 매개변수로 dfs를 호출할 때 stack에 새로운 Frame이 생성된다.

생성된 Frame에는 매개변수로 들어온 root 노드의 reference 값이 포함되며 재귀하여 다시 dfs를 호출하기 직전에 메서드의 어느 부분까지 진행되었는지가 저장된다. 재귀하여 매개변수에 data = 2인 노드를 전달하며 dfs 메서드를 호출하면 Stack에 다시 Frame이 생성된다.

다시 한번 재귀하여 data = 4인 노드를 전달하며 dfs 메서드를 호출하면 Stack에 Frame이 생성된다.

data = 4인 노드의 자식 노드는 없으므로 다시 재귀하는 경우 매개변수가 null인 상태로 dfs를 호출할 것이다.

Stack에 새로운 매개변수가 null인 새로운 Frame이 생성되지만 이러한 경우 재귀하지 않으므로 바로 Stack에서 pop되어 사라지게 된다.

이후 data = 4인 Frame이 계속 진행되어 20번 라인까지 진행되고 자신의 오른쪽 자식도 null이기 때문에 매개변수가 null인 상태로 dfs를 호출할 것이다.

이전과 동일하게 Node가 null이기 때문에 더이상 재귀되지 않을 것이며 Stack에서 바로 pop된다.

data = 4인 경우의 Frame도 더이상 남아있는 작업이 없으므로 Stack에서 제거되고 data = 2인 Frame이 20 line까지 진행된다.

data = 2인 노드의 오른쪽 자식 노드인 data = 5인 노드가 매개변수로 dfs가 호출되고 새로운 Frame이 생성된다.

data = 5인 노드의 왼쪽 자식 노드와 오른쪽 자식 노드도 null이기 때문에 data = 4인 노드와 동일한 과정으로 Frame이 생성되었다가 사라지게 될 것이다.

이후 data = 2인 Frame도 더이상의 작업이 남아있지 않기 때문에 Stack에서 제거된다.

data = 1인 Frame에서 왼쪽의 모든 노드를 조회하였기 때문에 20라인까지 진행하여 data = 3인 오른쪽 자식 노드를 매개변수로 dfs를 호출하고 새로운 Frame이 생성된다.

이후의 과정은 data = 2인 노드의 자식 노드를 순회하는 과정과 동일하므로 생략한다.

---

참고한 강의: https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84