TIL25, 자료구조(2)

어제 학습한 내용들에 이어서 새로운 내용들을 학습해보자!

트리 순회 (Tree traversal)

특정 목적을 위해 트리의 모든 노드를 한번씩 방문하는 것.

A부터 Z로 구성된 트리 구조에서 S를 찾기위해
모든 노드를 방문하는 것이 트리 순회의 예시이다.

트리의 모든 노드를 순회하는 방법 세가지를 알아보자.

1. 전위 순회
   • 루트에서부터 왼쪽의 노드들을 순차적으로 순회한 뒤, 오른쪽 방향으로 다시 순회한다.
     
2. 중위 순회
   • 가장 왼쪽 끝에 있는 노드부터 순회하고, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동해서 마저 순회한다.
     
3. 후위 순회
   • 루트를 가장 마지막에 순회한다. 가장 왼쪽 끝에 있는 노드부터 순회하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.
     

   # 그래프의 탐색

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

그래프는 정렬되어 있지 않기 때문에, 하나씩 모두 방문하여 찾아야 한다.

그래프의 정점 탐색방법 2가지

1. BFS (Breadth-First Search)
   • 너비 우선 탐색
   • 주로 두 정점 사이의 최단 경로를 찾을 때 사용한다. 경로를 하나씩 전부 방문한다면, 최악의 경우에 모든 경로를 다 살펴보아야 한다. 첫번째 경로가 타겟 정점이어도, 다른 모든 경로를 살펴보아야 한다.
2. DFS (Depth-First Search)
   • 깊이 우선 탐색
   • 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다.
   • BFS보다 시간은 조금 오래 걸리지만 모든 노드를 완전히 탐색할 수 있다.
   • 하나의 경로를 끝까지 탐색한 후, 타겟 정점이 아니라면 다음 경로로 넘어가 탐색한다.
   • 하나의 경로를 끝까지 들어가서 확인한 후 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번 만에 경로를 찾을 수 있다.