0. 비선형 자료구조 완전탐색
비선형 자료구조는 1:1이 아니기 때문에 일반적인 방식으론 탐색하기 어렵다.
따라서 비선형 자료구조를 탐색하기 위한 방식인 BFS와 DFS를 알아보도록 하자.
코드 구현은 간단하게 트리 형태를 2중 리스트를 통해 구현할 예정이다.
해당 알고리즘은 방문 여부를 체크하면 그래프, 2차원 배열 등에서도 사용된다.
1. 너비 우선 탐색(Breadth First Search, BFS)
루트 노드의 자식 노드들을 먼저 모두 차례로 방문한 후에, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식
인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로 선입선출 형태의 자료구조인 큐를 활용한다.
2. 깊이 우선 탐색(Depth First Search, DFS)
루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서 다른 방향의 노드로 탐색을 계속 반복하여 결국 모든 노드를 방문하는 순회방법
가장 마지막에 만났던 갈림길의 노드로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 재귀적으로 구현하거나 후입선출 구조의 스택 사용해서 구현
반응형