[자료구조/알고리즘] 211014 자료구조 BFS / DFS 기초개념 복습

📌 트리순회

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다. 트리순회도 3가지로 나눠지는데 전위순회, 중위순회 그리고 후위 순회이다.

• 전위순회
  가장 먼저 방문하게 되는 노드는 루트이며 왼쪽의 노드들을 우선으로 순회하며, 왼쪽에 위치한 노드를 다 돌면 오른쪽 노드를 탐색한다.
• 중위순회
  루트를 가운데 두고 순회한다. 루트를 기점으로 왼쪽에 위치한 노드들을 우선적으로 순회하고. 그다음엔 루트 방문, 마지막으로 오른쪽에 위치한 노드들을 순회한다.
• 후위순회
  루트를 가장 마지막헤 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문합니다.

이것을 코드로 단적인 예를 들자면 아래와 같다.

📌 BFS / DFS

1) BFS (너비우선탐색)

두 정점 사이의 최단 경로를 찾을 때 사용.
노드를 기준으로 목적지까지 가는 방법을 가까운 정점부터 탐색. 그리고 더는 탐색할 정점이 없을 때, 그 다음 떨어져 있는 정점을 순서대로 방문.
ex) 두 정점 사이의 최단 경로를 찾을 때 사용

2) DFS(깊이우선탐색)

한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용. BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색가능하다.

내가 봤을 때 이러한 부분들을 알고리즘에 적용된 부분들을 보면서 이렇게 적용되는거구나 확인하는게 좋은 것 같다.