탐색 알고리즘 DFS / BFS

알고리즘 파트는 책 "이것이 취업을 위한 코딩테스트다 -나동빈" 책을 기반으로 제가 이해한부분을 정리하기 위해 작성되었습니다 .

 

그래프 구조

- 노드(Node)와 노드를 연결한 간선(Edge)을 모아놓은 자료구조. 노드는 vertex라고도 부른다.

- '노드가 인접하다' 라는 것은 두 노드가 간선으로 연결되어 있다라는 의미

- 그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것

그래프 구현 방법 

그래프를 구현하는 방법에는 인접행렬(Adjacency Materix)와 인접리스트(Adjacency List)방식이 있다. 두개의 구현 방식은 각각의 상반된 장단점을 가지고 있는데 대부분 인접리스트 형식을 많이들 사용한다.

1. 인접행렬 (Adjacency Matrix) : 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 연결되어 있지 않는 노드끼리는 무한(Infinity)의 비용이라고 작성한다.

2. 인접리스트 (Adjacency List) : 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다. 인접행렬에 비해 연결된 정보만을  저장하기 때문에 메모리를 효율적으로 사용한다 (= 메모리 공간 낭비가 적다). 하지만 인접 행렬에 비해 정보를 얻는 속도가 느리다. 연결된 데이터를 하나하나씩 확인해야 하기 때문이다. 

 

 

DFS (Depth-First Search) 깊이 우선 탐색

1. 탐색 시작 노드를 스택에 삽입하고 방문처리

2. 스택의 최상단에서 방문하지 않은 인접 노드가 있다면 그 인접노드를 스택에 삽입하고 방문처리 (일반적으로 방문하지 않은 인접노드가 여러개 일 경우 번호가 낮은 순서부터 처리한다)

2-1. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드 꺼냄

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

 

: 특정 노드에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색하는 알고리즘. DFS 탐색 알고리즘은 스택 자료구조에 기초한다. 실제로는 스택을 쓰지 않아도 된다. 데이터의 개수가 N개인 경우 O(N)의 시간복잡도를 가진다. 스택을 이용하기 때문에 재귀함수를 이용하면 간결하게 구현가능하다.

 

BFS (Breadth-Frist Search) 너비 우선 탐색

1. 탐색 시작 노드를 큐에 삽입하고 방문처리

2. 큐에서 노드를 꺼내 인접 노드 중에서 방문처리 하지 않은 노드가 있다면 모두 큐에 삽입하고 방문 처리한다.

3. 2번의 과정을  더 이상 수행할 수 없을 때까지 반복

 

: 즉 인접하는 노드 중 가까운 노드부터 탐색하는 알고리즘. deque 알고리즘을 사용하면 된다. 데이터 개수가 N개인 경우 O(N)의 시간복잡도를 가진다.