그래프

그래프 순회

그래프 탐색

• 깊이 우선 탐색 (Depth First Search)
  - Stack, 재귀로 구현
  • 백트래킹을 통해 뛰어난 효과를 보여줌
• 너비 우선 탐색 (Breadth First Search)
  - Queue로 구현
  • 그래프 최단 경로 구하는 문제

백트래킹

백트래킹(Backtracking)
해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙)해 정답을 찾아가는 범용적인 알고리즘
특히 제약 충족 문제에 유용함

DFS와 상당히 밀접한 관계
DFS => 백트래킹의 골격을 이루는 알고리즘

주로 재귀로 구현함
최악의 경우 모든 경우를 다 봐야함 => 브루트 포스와 유사
but 운 좋으면 정말 빨리 끝남.

가지치기 = Pruning

제약 충족 문제(Constraint Satisfaction Problem, CSP)

수많은 제약 조건을 충족하는 상태를 찾아내는 문제
백트래킹이 문제 해결에 필수적으로 요구됨

대표문제 : 스도쿠, 십자말풀이, 8퀸문제 등