[CS 기초] Trees Basics | 트리 알고리즘 기초 | DFS Depth First Search 이론 | 깊이 우선 탐색
트리는 정말 어렵다. 트리는 정말 진짜로 어렵다.
DFS (Depth First Search) 깊이 우선 탐색
DFS는 STACK 이라는 자료 구조를 사용한다. STACK은 FIRST IN LAST OUT이다.
DFS 탐색을 시작한다.
- Root node V 부터 시작한다. Stack에 V 노드를 넣는다.
- V 노드를 current로 옮기고 방문경로로 옮기는 순간 V노드에 연결되어있는 2개의 노드를 Stack에 추가한다.
E를 넣고 A를 넣는 이유는 Stack은 마지막으로 들어간 노드가 먼저 나오기 떄문이다.
- Stack에 제일 마지막에 들어온 A를 Current 로 옮긴다.
- Current에 있는 A를 방문경로로 옮기는 순간 A와 연결된 노드 C를 Stack에 넣는다.
- Stack에 있던 C를 current로 옮긴다,
- Current에 있던 C를 방문경로로 옮기는 순간 C와 연관된 노드를 Stack에 추가하려 하지만 C와 연결된 노드가 없다.
그러면 Stack에 아무것도 추가되지 않는다,
- Stack에 있던 E를 current로 옮긴다.
- Current에 있던 E를 방문경로로 옮기는 순간 E와 연관된 노드 B와 R을 Stack에 추가한다.
- Stack에 있던 B를 current로 옮긴다.
- Current에 있는 B를 방문경로로 옮기는 순간 B와 연관된 노드를 Stack에 추가하려 하지만 연관된 노드는 없다.
- Stack에 있던 R를 current로 옮긴다.
- Current에 있는 R를 방문경로로 옮기는 순간 R와 연관된 노드를 Stack에 추가하려 하지만 연관된 노드는 없다.
위 트리의 DFS는
V A C E B R
출처 : 인프런 눈떠보니 코딩 테스트 전날