[TIL] 백트래킹 BackTracking

 

9663 N-Queen 을 풀다가 알고리즘 분류에 백트래킹이 있길래 한 번 개념을 정리해 본다 

백트래킹 BackTracking

재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드 (상태) 가
제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 
그 노드를 제외 (포기) 하고 다음 단계로 나아가는 방식

 

쉽게 말해, 현재 상태에서 가능한 모든 다음 상태를 탐색하다가

조건에 맞지 않는 상태를 발견하면 그 상태를 배제하고,

이전의 상태로 돌아가서 다른 가능한 경우를 탐색하는 방식이다 

 

백트래킹 문제는 DFS (Depth-First Search 깊이 우선 탐색) 로 접근할 수 있다 

DFS 는 그래프나 트리의 모든 노드를 깊이 있게 탐색하며

조건에 맞지 않으면 바로 이전 상태로 돌아가서 다른 경로를 탐색하는 알고리즘이다

 

DFS 와 BFS 의 차이

BFS 는 Breathed First Search - 너비 우선 탐색 알고리즘

시작 정점부터 시작하여 인접한 모든 정점들을 우선 방문하고, 

더 이상 방문할 정점이 없으면 한 단계 깊이 내려가서 다시 인접한 모든 정점들을 우선 방문한다 

정리하면, 현재의 깊이 레벨에서 모든 정점을 먼저 탐색한 후, 다음 깊이 레벨로 이동한다 

DFS 는 시작 정점을 방문한 후 자식 정점을 모두 탐색한다,

이 때 더 이상 연결된 자식 정점이 존재하지 않을 때까지 탐색을 계속한 후

한 단계 이전으로 돌아가서 다시 다른 자식 정점들을 탐색한다

정리하면, DFS 는 가능한 한 깊이 탐색한 후, 되돌아가면서 나머지 정점들을 탐색한다 

출처 https://velog.io/@vagabondms/DFS-vs-BFS