자료구조 ( Tree, Graph, BST, BFS, DFS )

---

Tree Traversal   

 

전위 순회

가장 먼저 루트를 방문하고, 루트에서 시작해 왼쪽 노드부터 먼저 둘러본 뒤, 왼쪽 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.

 

중위 순회

루트를 가운데에 두고 순회한다.
제일 왼쪽 끝에 있는 노드부터 순회하기 시작해
루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색합니다.

 

후위 순회

루트를 가장 마지막에 순회한다.
제일 왼쪽 끝에 있는 노드부터 순회하기 시작해
루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문합니다.

 

BFS / DFS   

 

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적이다.

 

BFS: Breadth-First Search, 너비 우선 탐색이라고 합니다.  큐를 사용한다.

DFS: Depth-First Search, 깊이 우선 탐색이라고 합니다.  스택을 사용한다.

 

---

 

자료구조   

 

문제 풀이에 들어가기에 앞서 문제에서 요구하는 바가 무엇인지 파악하고, 어떤 자료구조를 쓸 것인지 생각하기

 

이 문제는 어떤걸 써서 풀지? 라기 보다는
요구하는 바를 파악하는데 힘을 쓴다면 자연스럽게 어떠한 자료구조와 연관이 되는지 생각할 수 있다.

 

---