CS : Algorithm : DFS & BFS

탐색 알고리즘

 

1.

그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘

 

2.

그래프 : 정점과 간선으로 구성된, 한정된 자료구조. 각각의 지점을 정점이라고 하고, 정점과 정점의 연결을 간선이라고 한다.

 

3.

그래프가 주어지고, 특정 정점과 다른 정점 간 이동이 가능한가? 또는 이동할 수 있다고 했을 때 해당 경로는 효율적인가? 등을 따질 때 사용되는 알고리즘이 탐색 알고리즘이다.

 

 

 

---

 

 

DFS (깊이 우선 탐색)

 

 

출처 https://developer-mac.tistory.com/64

 

1.

가장 직관적이고, 구현하기 쉬운 탐색 방법

 

2.

현재의 정점과 연결된 정점들을 하나씩 갈 수 있는지 검사하고, 특정 정점을 갈 수 있다면 그 정점에 가서 같은 행위를 반복한다. 갈 수 없다면, 이전 정점으로 돌아간다.

 

3.

같은 정점을 다시 방문하지 않도록 정점에 방문했다는 것을 표시해준다.

 

4.

2차원 배열을 활용하여 구현한다면, 1) 이전에 방문한 적이 있는지, 2) 해당 위치가 배열의 index를 벗어나는지를 체크할 필요가 있다.

 

5.

재귀 함수를 통해 구현되기 때문에, 단순하고 직관적이다.

 

6.

재귀 함수를 사용하므로 인해, 함수 호출 비용이 발생한다.

'깊이'가 지나치게 깊다면, 메모리 사용 비용이 많이 발생되고 예측하기 어렵다. 따라서, data 크기가 일정 이상이라면 DFS를 사용하지 않는 것이 좋다.

마지막으로, '최단 경로'를 알 수 없다.

 

 

 

---

 

 

BFS (너비 우선 탐색)

 

출처 https://developer-mac.tistory.com/64

 

1.

시작점에서 가까운 정점부터 순서대로 방문하여 탐색하는 알고리즘

 

2. 

queue를 사용하여 구현한다.

 

3.

다음 과정을 반복한다.

• 시작점을 queue에 push한다.
• queue의 맨 앞 정점을 pop한다.
• pop한 정점과 연결된 정점을 queue에 push한다.
• pop한 정점이 목표로 하는 정점이라면 반복을 종료한다.
• 또는 더 이상 갈 수 있는 정점이 없거나, queue가 비었다면 반복을 종료한다.

 

4.

BFS는 효율적인 운영이 가능하고, 시간 또는 공간 복잡도 측면에서 안정적이다.

또한, 간선의 비용이 모두 같다면, 최단 경로를 구할 수 있다.

만약, 간선의 비용이 다르다면, 다익스트라 알고리즘 등을 활용해야 한다.

 

5.

단점으로는, 코드 구현이 조금 더 어렵고, 모든 지점을 탐색할 경우를 대비하여 queue의 메모리가 미리 준비되어야 한다.

 

 

 

---

 

DFS와 BFS 비교