오늘은 알고리즘에서 가장 중요한 개념중에 하나인 DFS에 대해 설명을 드리고자 한다.
DFS는 다양한 경우의 수를 구할때 굉장히 많이 쓰이는 알고리즘이나 꼭 익혀두길 권장한다.
일단 코드소스를 먼저 보여드리겠다.
public class DFS {
public static void main(String args[]) {
DFS tree = new DFS();
Node root = new Node(1);
root.lt = new Node(2);
root.rt = new Node(3);
root.lt.lt =new Node(4);
root.lt.rt = new Node(5);
root.rt.lt = new Node(6);
root.rt.rt = new Node(7);
tree.dfs(root);
}
public void dfs(Node root) {
if(root == null) return;
else {
//System.out.println(root.data); 전위 순회
dfs(root.lt);
//System.out.println(root.data); 중위 순회
dfs(root.rt);
//System.out.println(root.data); 후위 순회
}
}
}
class Node {
int data;
Node lt;
Node rt;
public Node(int data) {
this.data = data;
this.lt = null;
this.rt = null;
}
}
여기서 dfs 함수 내부를 보면 아시겠지만 재귀함수가 사용되는것을 볼 수 있다. 재귀함수에 대해 잘 모르시는 분이라면 아래글을 참고하자.
https://devkingdom.tistory.com/262
public static void main(String args[]) {
DFS tree = new DFS();
Node root = new Node(1);
root.lt = new Node(2);
root.rt = new Node(3);
root.lt.lt =new Node(4);
root.lt.rt = new Node(5);
root.rt.lt = new Node(6);
root.rt.rt = new Node(7);
tree.dfs(root);
}
다시 코드로 가서 메인에 내가 입력한 코드는 트리를 만드는 것인데 여기서 tree를 만든것을 표현하면 아래의 그림과 같이 보일 것이다.
여기서 main 의 맨 아랫줄에 호출한 dfs함수가 호출되게 되면 이제 탐색을 시작한다.
오늘은 전위, 중위, 후위 순회 중에 전위만 스택프레임이 쌓여서 처리되는 것을 확인해볼까한다. 나는 흘러가는 구조를 익히기 위해 직접 다그려보았다... 여러분들도 한번 쭉 그려보면 좋을 것 같다.
링크로 첨부한 재귀함수 호출 방법을 안다면ㄴ 위의 그림처럼 스택 프레임이 왜 저렇게 동작하는지를 알 수 있을꺼다. 다시 한번 말씀드리지만 ... 꼬옥 그려보길 권장드린다.
끝.
반응형
'Develop > Algorithm' 카테고리의 다른 글
백트래킹 (Back Tracking) 알고리즘 이해하기 (0) | 2021.07.29 |
---|---|
BFS (Breadth-First Search) 알고리즘 정리 (0) | 2021.07.28 |
재귀 함수 정리 (0) | 2021.07.27 |
병합 정렬 (Merge Sort) (0) | 2021.07.06 |
퀵 소트 (Quick Sort) (0) | 2021.07.05 |
댓글