✏️ DFS와 BFS의 구현방법과 차이 설명
아래글에 설명해두었으니 이 내용은 여기서 확인바란다.
백준 1260: DFS와 BFS 해설- python
✏️ 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에..
duckracoon.tistory.com
✏️ DFS와 BFS 각각 어떤 상황에서 사용할까?
어떤 문제를 풀때 DFS를 써야할지, 어떤 문제를 풀때 BFS를 쓸지 난감한 경험때문에 정리한다.
When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?
I understand the differences between DFS and BFS, but I'm interested to know when it's more practical to use one over the other? Could anyone give any examples of how DFS would trump BFS and vice...
stackoverflow.com
위는 부족하면 참고하라
DFS와 BFS의 특징을 명확하게 이해하고 있어야한다. 그 특징에따라 사용에 더 적합한 문제유형들이 있다.
1) 그래프의 모든 정점을 방문해야하는 문제
DFS, BFS 뭐든 상관없다. 편한걸 쓰면 된다.
2) 경로의 특징을 저장하는 문제
예시로 각 정점에 숫자가 있고 a부터 b까지 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제. 각각의 경로마다 그 특징을 저장해두어야하는 문제는 DFS를 사용한다.
3) 최단거리를 구하는 문제
미로찾기등 최단거리를 구하는 경우 BFS가 좋다. DFS로 경로를 탐색하면 처음 발견하는 해답이 최단거리가 아닐수도 있지만 BFS는 현재노드에서 가까운 곳부터 찾기 때문에 경로를 탐색시 먼저 찾아지는 해답이 곧 최단거리다.
4) 검색대상그래프가 많이 클때DFS가 좋다고한다.
5) 검색대상의 규모가 별로 크지않고 검색시작지점으로부터 원하는 대상이 별로 멀지 않으면 BFS.
'프로그래밍 > 자료구조 & 알고리즘' 카테고리의 다른 글
| NQueen 문제 파이썬과 자바스크립트 풀이 (0) | 2022.02.19 |
|---|---|
| 백트랙킹 기법 정리 (0) | 2022.02.19 |
| 파이썬 collections deque 사용법과 응용 (0) | 2022.02.06 |
| 파이썬 heapq 모듈 사용법과 응용 (0) | 2022.02.05 |
| 그리디 알고리즘 개념정리와 문제 (0) | 2022.02.05 |