250x250
Notice
Recent Posts
Recent Comments
Link
코린이의 기술 블로그
BFS, DFS 본문
BFS, DFS 는 그래프를 탐색하는 방식입니다.
그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이어진 관계로 보면 됩니다:)
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 반복한다는 개념입니다. 일종의 가지치기의 개념을 생각하면 좋습니다.
DFS(깊이우선탐색)
- 현재 정점에서 점들까지 이어가면서 탐색
- 스택 또는 재귀함수를 사용
BFS(너비우선탐색)
- 현재 정점에서 연결 된 가까운 점에서 탐색
- 큐를 이용해서 사용
경로의 특징을 저장해둬야 하는 문제
각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다.
최단거리 구해야 하는 문제, 미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다. 왜냐면 경로를 읽지 못하므로 더 유리합니다.
경로가 있는 가지치기로 보면 좋을 것 같습니다:)
728x90
'Java Web' 카테고리의 다른 글
스프링 폼 요소 - 1 (0) | 2021.12.07 |
---|---|
데이터 전달자 모델 (0) | 2021.12.06 |
컨트롤러 요청처리 (0) | 2021.12.03 |
컨트롤러 요청처리 (0) | 2021.12.02 |
String 문자열 오류 (0) | 2021.11.23 |