코린이의 기술 블로그

BFS, DFS 본문

Java Web

BFS, DFS

미늬온 2021. 12. 5. 22:37

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
Comments