DFS / BFS 개념

DFS / BFS

DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)은 그래프를 탐색하는 방법 중의 하나이다.

그래프란, 노드(node)와 노드를 연결하는 간선(edge)으로 이루어진 자료구조이다.

그래프를 탐색한다는 것은 하나의 노드로부터 시작하여 모든 노드를 방문한다는 뜻이다.

---

DFS(Depth-First Search)

루트노드(혹은 다른 임의의 노드)에서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 끝까지 탐색하는 방법이다.

• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
• 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
• 그래프를 탐색할 때 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 이를 검사하지 않을 경우 무한루프에 빠질 수 있다.

---

BFS(Breadth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다
• 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.
• 그래프를 탐색할 때 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다. 이를 검사하지 않을 경우 무한루프에 빠질 수 있다.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는(선입선출) 자료 구조인 큐(Queue)를 사용한다.

---

DFS BFS 비교

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

---

문제풀이

[알고리즘/문제] - 백준 11724 [연결 요소의 개수] - DFS/BFS

[알고리즘/문제] - 백준 16236 [아기 상어] - JAVA

[알고리즘/문제] - 백준 16234 [인구 이동] - JAVA

[알고리즘/문제] - 백준 12100 [2048 (Easy)] - JAVA