[알고리즘] BFS와 DFS란?

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

---

DFS는 그래프에서 깊은 부분을 우선적으로 탐색합니다.

한 정점에서 시작해 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용합니다.

특징

• 스택 자료 구조에 기초하며, 구현할 때 재귀 함수로 구현하는 것이 좀더 간편합니다.
• DFS를 구현할 때, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 검사하지 않을 시 무한 루프에 빠질 위험이 있으므로 반드시 검사해야합니다. ( visited[index] = true; )

• 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사합니다.
• 모든 경우를 하나하나 다 탐색을 해야될경우 사용합니다. ( 순열, 조합 구현 )
• 검색 속도 자체는 BFS에 비해 느립니다.

탐색 과정

( 파란색 : 이동방향, 초록색 : 탐색 순서 ) 

탐색 순서 : 1 -> 2 -> 3 -> 4 -> 5 ->  7 -> 6

구현 코드(재귀)

def dfs_recursive(graph, start, visited = []):
## 데이터를 추가하는 명령어 / 재귀가 이루어짐 
    visited.append(start)
 
    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)
    return visited

BFS (너비 우선 탐색, Bread First Search )

---

BFS는 그래프에서 가장 가까운 부분을 우선적으로 탐색합니다.

한 정점에서 가장 인접한 노드를 먼저 넓게 탐색하면서 깊이 내려가므로 DFS와는 정반대입니다.

특징

• 재귀적으로 동작하지 않습니다.
• BFS도 DFS처럼 노드 방문 여부를 반드시 검사해야합니다.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 선입 선출 자료구조 Queue를 사용합니다. (선입선출 원칙으로 탐색)
• 최단경로(다익스트라, 플로이드)를 찾는데 활용합니다.

탐색 과정

( 파란색 : 이동방향, 초록색 : 탐색 순서 )

탐색 순서 ( 큐에 들어간 순서 ) : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 

from collections import deque
def bfs(graph, start_node):
  		visit = list()
  		dq=deque()
  
       dq.append(start_node)
  
       while dq:
           node = dq.popleft(0)
           if node not in visit:
              visit.append(node)
              dq.append(graph[node])
 
      return visit

그렇다면 DFS와 BFS를 선택함에 있어 어떤 기준이 필요할까?(코테에서)

---

저의 개인적인 경험으로(저는 BFS를 선호합니다) 대부분의 경우 DFS와 BFS 어느것을 선택해도 무방한 문제들이 많습니다

• 저는 보통 DFS는 재귀적인 특징과 백트래킹을 이용한, 모든 경우를 하나하나 전부 탐색하는 완전탐색 문제를 풀때 선호하고(대표적으로 조합 순열 구현)
• BFS는 depth(깊이)특징을 이용한 문제(대표적으로 최단경로)를 풀어야할때 선호합니다.

참고 블로그

https://hstory0208.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS%EC%99%80-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/DFS%20%26%20BFS.md