DFS vs BFS

[Sam1000won]

BFS DFS 공부를 하다가 문제 해결방법에 무엇이 좋을까 막연한 궁금증이 생겼다.
기본 적인 정의를 공부하고 어떤식으로 풀어 나갈지 생각해보았다.

BFS (Breadth-First Search):

장점:

• 무향 그래프에서 최단 경로 찾기에 효율적
• 모든 노드를 레벨별 방식으로 방문하도록 보장
• 그래프의 연결성 판단에 사용 가능

단점:

• 깊은 그래프의 경우 DFS에 비해 메모리 소비가 더 많을 수 있음
• 백트래킹 문제나 사이클 찾기에 효율적이지 않음

DFS (Depth-First Search):

장점:

• 트리 구조 탐색에 효율적, 특히 원하는 요소가 루트에 가까울 때
• 백트래킹 문제 및 사이클 찾기에 사용 가능
• 특정 상황에서 BFS보다 메모리 소비가 적음

단점:

• 그래프에서 최단 경로 찾기에 효율적이지 않을 수 있음
• 트리의 깊은 가지에 갇혀 더 가까운 해결책을 놓칠 수 있음

공부

공통점:

• DFS와 BFS는 모두 연결된 구성 요소를 탐색하고 검색하는 데 사용되는 기본적인 알고리즘이다

차이점:

• 노드 방문 방식과 그래프 탐색 순서가 다르다.
• DFS 깊이 탐색을 우선으로 하며 백트래킹을 하여 다른 경로를 탐색
• BFS 폭 탐색을 우선으로 하며 현재 레별의 모든 노드를 탐색, 나무 계층별로 탐색
• DFS 노드 재방문 가능 BFS 재방문 불가
• DFS 트리구조 BFS 그래프의 연결성
• 깊이가 깊은 경우 DFS 메모리 할당이 비효율 적임
• 폭이 넖을 경우 BFS 비효율
• 완전성에서 서로 비슷하다.

결론

• 트리 구조에는 DFS가 적합하다.
• 무향 그래프에는 BFS가 적합하다.
• 그래프 구조가 사이클이 적다면 DFS를 사용하는 것이 좋지만 연결성이 밀집되어 있다면 BFS 사용하는 것이 좋다.
• 정답이 트리 구조이고 깊이가 낮다면 DFS가 효율적이고 최단 경로를 찾는다면 BFS를 사용하는 것이 효율적이다.
• 따라서 문제의 해결 방법은 문제를 분석하고 어떤것이 올바른지 확인하여 어떤 알고리즘을 선택할지 고르는 것이 적절하다.