탐색 알고리즘 DFS / BFS

1. DFS(Depth - First Search)

깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

그래프는 노드와 간선으로 표현되며, 두 노드가 간선으로 연결되어 있다면 두 노드가 "인접하다"라고 표현한다.

스택이나 재귀함수로 구현 가능

모든 경우의 수를 탐색하고자 하는 미로 문제에 적합

 

1. 인접행렬 방식

2차원 배열로 그래프의 연결관계를 표현하는 방식

연결되지 않은 정보도 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비됨

노드 번호로 바로 접근 가능하므로 인접리스트에 비해 정보를 얻는 속도가 빠름

2. 인접리스트 방식

노드에 연결된 정보만을 리스트로 추가하는 방식

연결된 정보만 저장하기 때문에 메모리를 효율적으로 사용

인접행렬 방식에 비해 연결된 데이터를 하나씩 확인해야 하기 때문에 정보를 얻는 속도가 느리다.

 

 

2. BFS(Breadth - First Search)

너비 우선 탐색이라는 의미를 가지며, 가까운 노드부터 탐색하는 알고리즘

인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성

최단경로 문제를 해결할때 적합

시간복잡도 O(N)

일반적인 경우 실제 수행 시간은 DFS보다 좋은편임