[알고리즘] BFS, DFS, 백트래킹 정리

현재 진행중인 자바 알고리즘 스터디에서 BFS, DFS, 백트래킹 정리를 맡아 블로그에 정리해보려한다.

BFS, DFS는 지금껏 알고리즘 공부를 하면서 항상 골머리를 앓게 한 파트였기에 이렇게 정리하는 시간을 가짐으로써 조금 더 알고리즘과 가까워질 수 있지 않을까 싶다.

 

BFS와 DFS는 그래프 탐색이라는 큰 범주에 속한다. 우선 BFS, DFS를 알아보기 전에 그래프가 무엇인지 먼저 살펴보자.

 

그래프란?

노드와 그 노드를 잇는 간선을 하나로 모아놓은 자료구조.

 

그래프 탐색이란?

그래프의 모든 노드를 탐색하기 위해 간선을 따라 순회하는 것.

탐색 방법에 따라 BFS(Breadth First Search)와 DFS(Depth First Search)로 나뉘어짐.

 

BFS(Breadth First Search)

그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘

너비 우선 탐색, 같은 레벨에 있는 정점들은 같이 탐색.

순차탐색 이후 다른 자식의 자식을 확인하기 위해 큐(선입선출)를 사용.

 

DFS(Depth First Search)

깊이 우선 탐색, 한 노드에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색. 즉, 최대한 깊이 탐색한 후 빠져나오는 것.

백트래킹의 일종으로, 스택(후입선출)과 재귀를 활용.

 

[백준] BFS와 DFS #1260

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

• 해당 알고리즘들은 트리구조의 알고리즘 뿐만 아니라 모든 알고리즘에 적용될 수 있다.
• BFS는 최단경로 문제, 가중치가 없는 그래프 문제에 적합하다. 
• DFS는 가중치 관련 문제, 탐색에 대한 제약 조건이 있는 문제에 적합하다. 

 

백트래킹(BackTracking, 퇴각검색)

DFS를 우선 실행하고 더 이상 탐색을 진행할 수 없는 상황이면 다시 되돌아가서 탐색을 진행하는 것.

 

[참고자료]

그래프탐색 (DFS, BFS)

https://github.com/VSFe/Algorithm_Study/blob/main/Concept/New/06_Graph_Traversal/Ch.06_%EA%B7%B8%EB%9E%98%ED%94%84_%ED%83%90%EC%83%89.pdf

DFS

https://blog.encrypted.gg/942

BFS

https://blog.encrypted.gg/941