BFS와 DFS의 차이점을 알려주세요
알고리즘 공부를 하다보면 깊이우선탐색 (BFS) 이나 넓이우선탐색 (DFS) 라는 말들이 나오는데요.
이 둘의 차이점이 뭘까요?
실제로 BFS와 DFS는 언제 어떻게 다르게 쓰이는 걸까요?
안녕하세요 DFS와 BFS 알고리즘은 아시다시피 탐색 알고리즘입니다.
어떠한 그래프가 주어졌을때 어떠한 형태로 노드들을 탐색할것인가의 차이가 DFS와 BFS의 차이라고 볼수 있습니다.
그래프라고 하면 거창해 보이지만 실생활에서 적용해 보면,
경로가 표시된 지도 혹은 윷놀이판 등에서 최단거리 혹은 다양한 경로를 탐색하는데 있어서
아주 유용한 알고리즘이라고 볼수 있습니다.
DFS라 하면 D는 Depth 의 약어로써 깊이 우선 탐색이라고 불립니다.
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로써 자식노드(branch)를 모두 탐색한후
다음 형제노드로 넘어가는 방식입니다.
BFS는 Breadth First Search의 약어로써 넓이 우선 탐색이라고 불립니다.
그래프에서 시작노드의 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다.
시작지점부터 가능한한 넓게 탐색하기 때문에 두 노드사이의 최단경로를 찾을수가 있는 형태이지요
개념적으로는 위와같고 더욱 이해가 편하기 위해서는
알고리즘 문제를 보고 직접 코딩해보는게 더 와닿을수 있을것 같습니다.
추가적으로
DFS는 후입선출인 Stack 자료구조를 이용하고 BFS는 선입선출인 Queue 자료구조를 이용하는
차이점도 있을수 있겠네요-
각기 장단점이 있고 쓰여지는 용도가 달라서 둘다 공부해두시면 도움이 많이 되실겁니다.
DFS는 깊이우선탐색으로 루트 노드에서 브랜치별로 자식노드를 끝까지 탐색하고 다음 브랜치로 넘어가는 탐색방법이며 BFS는 너비우선탐색으로 루트에서 브랜치 구분없이 가장 가까운 노드를 먼저 탐색하고 멀리 떨어져 있는 노드를 나중에 방문하는 탐색방법으로 두 노드사이의 최단경로를 찾고 싶을 때 주로 사용합니다.
미로탐색의 경우 최단 거리만을 가지고 탈출하는 것이기에 BFS모델이 적합 합니다.
하지만, 같은 미로탐색이라도 이동할때마다 가중치나 제약이 생길 경우 가중치 변수에 대한 지속적 관리를 위해 시간이 더 걸리더라도 DFS로 구현하는게 변수값을 통한 결과 도출에 더 유리하게 됩니다.
다른 예로 경찰이 범인을 찾기 위해 주변인 조사를 할 때는 모든 관계를 다 살펴보는 DFS보다는 가장 가까운 관계부터 탐색하는 BFS가 더 효과적일 수 있습니다.
때문에 어떤 알고리즘이 더 좋다 나쁘다고 할 수 없고 상황과 여건에 유리한 알고리즘을 택해서 사용해야 합니다.
도움이 되셨기를 바랍니다.
둘의 차이는 아래와 같습니다.
DFS : 트리를 탐색할 때 자식을 먼저 탐색하는 알고리즘
BFS : 트리를 탐색할 때 형제를 먼저 탐색하는 알고리즘
DFS는 BFS에 비해 제작하기 간단하지만 BFS가 속도면에서 더 유리합니다.
두 알고리즘 모두 연결된 그래프르르 탐색하는데 사용되나, DFS 의 경우 특정 조합을, BFS 의 경우 최단거리를 찾는데 유용합니다.
※ 깊이 우선 탐색(DFS)의 특징
- 자기 자신을 호출하는 순환 알고리즘의 형태를 지님
- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것 (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있음)
※ 너비 우선 탐색(BFS)의 특징- BFS 는 재귀적으로 동작하지 않는다.
- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.
- BFS 는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용함
- 즉 선입선출(FIFO) 원칙으로 탐색
Ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash 와 Vanessa 사이에 존재하는 경로를 찾는 경우
* 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야할지도 모름
* 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
BFS(Breadth-First-Search)의 경우 너비우선탐색,
DFS(Depth-First-Search)의 경우 깊이우선탐색을 의미하는 것은 질문자님께서 잘 알고 계시네요.
이는 트리(Tree) 자료구조를 순회하는 방법에 관한 것으로,
실제 코딩테스트 문제에서 자주 출제되는 알고리즘 중 하나입니다.
두 알고리즘을 설명드리기 전, 우선 트리(Tree)자료구조에 대해 간단히 설명드리겠습니다.
트리구조는 노드(Node) 와 링크(Link)로 구성된 자료형태를 말하며, 현실세계에서도 많이 찾아볼 수 있는 자료구조입니다.
회사의 조직도가 대표적인 트리구조로 짜여있다고 볼 수 있습니다.
이 트리구조를 모두 순회한다는 것은, 특정한 노드를 기점(출발점)으로 하여, 다른 모든 노드를 방문한다는 의미입니다.
이렇게 모든 노드를 방문하는 방법이 대표적으로 두 가지, 너비우선탐색과 깊이우선탐색이 존재하는거죠.
[너비우선탐색]
너비우선탐색은 말 그대로, "너비를 우선으로 탐색"한다는 의미입니다. 여기서의 너비는 "형제"를 의미하는데, 쉽게 말해서 트리구조에서 같은 차수(Degree)에 속하는 노드를 모두 형제로 볼 수 있습니다. 위 그림에서는 [B,G], [A,D,I], [C,E,H]가 형제겠네요.
위의 그림과 같은 Tree를 순회하며, 시작 노드를 F노드로 한다면 너비우선 탐색에서는 F->B->G->A->D->I->C->E->H 순으로 순회하게 됩니다.
[깊이우선탐색]
깊이우선탐색 또한 말 그대로 "깊이를 우선으로 탐색"한다는 의미입니다. 여기서의 깊이는 "자식"을 의미합니다. 위의 그림에서는 F의 자식이 [B,G]가 있고, B의 자식으로는 [A, D]가 있고... 이렇게 되겠네요. 깊이우선탐색에서는 트리를 순회할 때 자식노드(Child Node)가 없을 때까지 깊게 파고들어간 후, 없다면 다시 부모 노드(Parent Node)로 올라간 후 다시 자식 노드(Child Node)가 있는지 확인하고, 없다면 다시 부모노드로 올라가는 형태를 반복합니다.
위의 그림과 같은 Tree를 순회하며, 시작 노드를 F노드로 한다면 깊이우선 탐색에서는 F->B->A->D->C->E->G->I->H 순으로 탐색을 하게 됩니다.
안녕하세요
DFS & BFS 차이점에 대해 질문 주셨는데요
두가지유형의 개념부터 설명 드리면
DFS : 트리를 탐색할 때 자식을 먼저 탐색하는 알고리즘
BFS : 트리를 탐색할 때 형제를 먼저 탐색하는 알고리즘
으로 말할수 있습니다.
모든 경우의 수를 구해야 하는 경우라면
DFS나 BFS 나 상관없이 편한 것을 사용하면 되지만,
이동과정에서 여러가지 제약이 있을 경유에는 DFS로 구현하는 것이 좋고
만약 최단거리를 구해야 하는 경우에는 BFS 가 훨씬 유리하다.
감사합니다
깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 2가지 방식 모두 모든 정점을 한번만 방문한다는 같은 목표를 가지고 있지만, 그 과정에서 탐색하는 방식의 차이가 있습니다.
깊이 우선 탐색은 인접한 부분부터 탐색하고,
너비 우선 탐색은 너비를 기준으로 탐색합니다.
이름 그대로, 깊이, 너비를 기준으로 탐색하고 있는데 DFS는 스택을 사용하고, BFS는 큐를 사용합니다.
