반응형
DFS/BFS 둘 중 어느것을 사용해서 문제를 풀어야 할까?
BFS / DFS
그래프의 모든 정점을 방문하는 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없다.
DFS
01 특정 경로를 찾는 경우
A부터 B까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제 등 각각의 경로마다 특징을 저장해야 할때는 DFS사용한다. BFS는 경로의 특징을 가지지 못한다.
02 백트래킹
모든 가능성을 찾아 현재 시점에서 더 이상 진행할 수 없는 경우 이전 단계로 돌아가 다른 가능성을 탐색할 때 사용된다.
03 사이클 검출
그래프에서 사이클이 존재하는지 검출하는 문제
04 트리 구조 검색
트리에서 특정 노드를 찾거나 특정 조건을 만족하는 노드를 찾을때
BFS
01 최단 경로 찾기
깊이 우선탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단 거리가 아닐 수 있지만 너비 우선탐색으로는 현재 노드에서 가까운 곳부터 찾기 때문에 곧 최단 거리가 된다.
02 레벨 순서 탐색이 필요한 경우
그래프의 레벨 순서대로 탐색하는 경우
03 최소 연결성 문제
연결된 구성 요소를 찾거나 최소 연결성을 찾아야 하는 경우
반응형
'코딩테스트 준비 > 자료구조 & 알고리즘' 카테고리의 다른 글
| C# - 우선순위 큐(Priority Queue)와 힙(Heap) (0) | 2024.03.16 |
|---|---|
| C# - 메서드안에서 재귀호출시 실행과정을 알아보자 (0) | 2023.12.22 |
| C# - Where와 Count를 사용해서 배열에 특정 요소의 개수 구하기 (0) | 2023.12.15 |
| C# - 완전 탐색(Brute force, 백트래킹,순열 조합,비트 마스크) (1) | 2023.12.08 |
| C# - 모듈러 연산(나머지 분배 법칙) (1) | 2023.12.04 |
댓글