7.29 Dev.Feedback (자료구조 Graph, Tree, DFS, BFS)
오늘은 다양한 자료구조중 Graph, Tree 그리고 DFS, BFS를 정리한다.
그래프와 트리는 다양한 복잡한 문제를 해결하는데 사용되는 비선형 데이터 구조이다. 두 구조의 차이점을 정확히 이해하고 넘어가야 할 것 같다. 먼저 그래프는 방향, 무방향 그래프 두 가지가 존재한다. 그 말은 어떤 정점과 정점 사이의 관계를 나타내는데 포인트가 있다는 것이다. 트리는 수 많은 그래프중의 하나인데, 특징은 방향 루트에서 아래로 내려가는 방향 그래프만 가능하다는 것이다. 이런 특징때문에 트리가 계층을 잘 보여주는 그래프로 표현된다.
그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search)이 있다.
BFS(너비 우선 탐색)
최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동하며 탐색하는 방식
루트 노트 또는 우리가 기준으로 잡은 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다.
시작 정점으로부터 가까운 정점을 먼저 방문하여 탐색 후 그 다음 레벨의 정점으로 넘어가 탐색하는 순회 방법이다.
주로 두 노드 사이의 최단경로를 찾고 싶을 때 선택한다.
BFS 수행 방법
1. 시작 정점을 방문한다 now
2. 정점의 인접 정점 중, 방문하지 않은 정점은 Queue에 저장한다.
3. Queue를 dequeue하여 그 값을 시작 정점으로 설정해주고, 1을 반복한다.
4. Queue가 Null이 되면 종료한다.
DFS(깊이 우선 탐색)
한 노드를 기준으로 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동하며 탐색하는 방식
루트 노드 또는 임의로 선택한 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 그 방향이 막혀있으면, 다시 가장 가까운 갈림길로 돌아와서 그 갈림길의 다른 방향으로 최대한 깊게 탐색을 진행하는 것 방식이 깊이 우선 탐색 방식이라고 할 수 있다.
BFS vs DFS
