[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

 

 

 

출처 : 인프런 눈떠보니 코딩 테스트 전날