이번 주는 탐색 알고리즘의 대표적인 두 가지 DFS와 BFS에 공부할 예정이다.
먼저 탐색 알고리즘은 트리 구조로 만들어진 그래프의 노드 그리고 노드와 노드 사이에 연결된 간선의 상태를 파악하기 위해 사용된다.
먼저, 그래프를 데이터로 구현하기 위해서는 먼저 테이블에 대한 이해가 있어야 하며, 이는 인접 행렬 또는 인접 리스트를 이용해서 구현할 수 있다.
[자료구조] 그래프(Graph)란 - Heee's Development Blog
인접 행렬이란 그래프의 연결 관계를 2차원 배열로 표현하는 방식을 말한다. 즉, 노드의 개수는 이미 정해져 있으니 각 ***노드(x축 index 번호)***와 노드(y축 index 번호) 사이의 관계를 데이터로 저장해 테이블로 구현한다는 의미이다. 그렇기 때문에 인접 행렬은 각각의 노드 간 관계를(논리 혹은 0,1) 파악하면 되기 때문에 **O(1)**의 시간 복잡도를 가진다.(n ~ m까지 모든 배열의 방의 관계를 파악한다.)
하지만 V개의 노드와 E개의 간선이 존재할 때 E개의 간선을 파악하기 위해서는 n ~ V까지 배열의 방을 파악하기 때문에 이는 O(V) 만큼의 시간 복잡도를 가진다. 즉, 불필요한 시간과 메모리를 소모한다는 단점이 있다.
인접 리스트란 리스트 자료형을 이용해 구현하는 방법이며 인접 행렬이 V개의 노드에서 E개의 간선을 파악하기 위해 O(V)만큼의 시간 복잡도를 가지는 단점을 개선하기 위해 고안된 방법이다. 이를 구현하기 위해서는 각 리스트의 index를 노드라고 가정하고 해당 노드에 연결되어 있는 노드의 번호를 저장한다. 그렇기 때문에 각 인덱스의 길이는 해당 노드에 연결된 노드에 대한 간선의 개수라는 뜻이다.
파이썬의 경우 자체에서 제공하는 리스트 자료형을 이용해 append() 함수를 활용하여 인접 리스트로 그래프를 구현할 수 있으며, C나 JAVA와 같은 언어는 표준 라이브러리에서 제공하는 List 클래스를 호출하여 구현할 수 있다.
[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog
DFS(Depth First Search), 깊이 우선 탐색이란 현재의 노드(혹은 루트 노드)와 인접한 노드들을 특정한 기준(ex.노드의 번호가 작은 순서대로)으로 인접한 노드의 제일 깊은 곳까지 탐색하며 모든 노드를 방문하는 것을 의미한다.
그렇기 때문에 DFS는 Stack 자료 구조나 재귀 함수를 통해 구현할 수 있으며 보통은 재귀 함수를 이용해 간결하게 코드를 작성한다.
깊이 우선 탐색의 경우 모든 노드 간 간선을 조회한다. 따라서,
의 시간 복잡도를 가진다. 그렇기 때문에 전체를 탐색하는 깊이 우선 탐색은 너비 우선 탐색보다 느리다.