DFS, BFS, 백트래킹(Backtracking)

BFS(Breadth-First Search)

• 계층/깊이 별로 순환탐색하는 방법
• 대표적 예) 친구 찾기 → 큐 이용
• 깊이마다 노드들을 우선순위에 따라 차례대로 넣고 큐에서 순서대로 꺼내어 순환을 하는 형태
• 자식 노드의 자식 노드를 탐색할 때, 메모리 소모가 크다. 트리의 깊이마다 노드들이 많고 트리가 넓을 때 등은 보통 사용하지 않는다.(최단경로 찾기나 찾는 노드가 인접할 경우 효과적)

---

DFS(Depth-First Search)

• 연결되어 있는 노드들의 우선순위에 따라 최대한 깊게 들어가는 방법
• 대표적 예) 전략 게임에서 하나의 수에 잇따른 가능성들을 파고 들때 사용 → 스택 이용 like 재귀함수
• 찾는 노드의 depth가 깊을 수록 빠르고, 메모리 소모가 적다.
• 깊이의 끝이 없거나 너무 깊이 들어가는 경우는 사용을 지양해야한다.(탈출불가)

---

한눈에 보는 DFS와 BFS

---

Backtracking(백트래킹)

• 완전탐색 : 여러 개의 solution을 가진 문제에서, 모든 solution을 탐색하는 전략
• 대표적 예 : 재귀 호출 or 스택을 통한 DFS

백트래킹의 원리

1. 어떤 노드의 유망성을 점검 후,
2. 유망하지 않으면 배제시킨다. = 가지치기
3. 해당 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. → 풀이시간 단축

---

N-Queens 구현과 백트래킹

• 헬퍼함수를 어떤 식으로 이용하여 '특정조건(유망성)'을 따질 것인가
  • n개만큼의 rooks 혹은 queens가 존재하는가?
  • 충돌이 존재하지 않는가?
• 조건에 부합하지 않는 경우는 어떤 식으로 넘어갈 것인가
  • 위 조건을 충족하지 않는다면, 다음 row 로 넘어가서 탐색을 진행하자.

유망성과 가지치기

• 유망성(Promising) : 가망이 있는가 없는가를 따지는 기준
• 가지치기(Pruning) : 유망성을 따져보고, 유망하지 않는 경우의 수는 배제하는 것으로 간단히 말하면 '불필요한 부분을 쳐낸다'로 보면 된다.

Backtracking & N-Queens
[알고리즘] 되추적(Backtracking)을 알아보자.
[알고리즘] Backtracking 이해하기
알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제