[DFS/BFS] 이해를 위한 기본 자료구조 및 알고리즘

꼭 필요한 자료구조 기초

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

- 그래프, 트리 등의 자료구조 안에서 탐색하는 문제를 자주 다룬다.

- 스택과 큐, 재귀 함수에 대한 이해가 전제 되어야 DFS/BFS를 잘 활용할 수 있다.

 

인접 행렬 vs 인접 리스트

1. 인접 행렬

    - 장점: 두 노드의 간선의 존재 여부를 바로 알 수 있다

    - 단점: 모든 관계를 기록함으로 노드의 개수가 많을 수록 불필요한 메모리 낭비가 일어난다

2. 인접 리스트

    - 장점: 연결된 것들만 기록하여 어떤 노드의 인접한 노드들을 바로 알 수 있다

    - 단점: 두 노드가 연결되어 있는지에 대한 정보를 얻는데 속도가 느리다.

 

인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프일 경우 사용

인접 리스트는 간선이 적은 희소 그래프일 경우 사용

 

DFS 

- 실제로는 스택을 사용하지 않지만 재귀함수로 스택의 기능을 수행한다

- 깊이 우선 탐색으로 모든 노드 탐색(완전탐색)시 사용한다.

- O(N)의 시간 복잡도를 가진다.

- 입력된 공간 혹은 방문 체크 리스트로 해당 노드를 방문 했는지 확인을 해야한다.

 

 

 

BFS

- 큐 자료구조를 사용해서 최단거리 탐색 시 사용한다.

- O(N)의 시간복잡도를 가지지만 일반적으로 DFS 보다 수행시간이 짧다.

- 입력된 공간 혹은 방문 체크 리스트로 해당 노드를 방문 했는지 확인을 해야한다.