탐색의 핵심

• 다중 For문 (4중 이상)이 생각난다면 재귀함수로 구현하고 → 재귀함수는 곧 DFS 구현의 초석이다.
• 완전탐색으로 풀기에는 시간복잡도가 10^6 이상인 경우가 많다.
  • 탐색을 하지 않아도 되는 조건을 다양하게 설계해서 복잡도를 줄인다.

완전탐색_DFS & BFS

• 어려운 탐색은 구현을 멈추고, 종이노트에 트리를 그려라!
  • 쉬운 탐색은 ‘Depth 마다의’ 또는 ‘Node 마다의’ 상태를 몰라도 풀린다.
  • 하지만 어려운 탐색은 ‘Depth 마다의’ 또는 ‘Node 마다의’ 상태를 자세하게 알아야 한다.
    • 필요시에는 Node 별로 현재 state를 관리하기 위해 node 별 struct 나 class가 요구된다.
      • :links: Github
• 재귀는 멈춰야 한다. 보통 그 조건은 Depth로 한다. 그러므로 모든 Node마다 Depth는 저장해야 한다.
• for문으로는 해결이 불가능한, 깊이가 달라지는 문제 구조
• input의 변수명은 무시하고 반드시 row와 col로 변수명을 선언해서 사용하고 Arr [row+1 , col+1] 배열을 이용한다.
• 둘 다 메서드를 만들고 visit 갱신, 값 갱신은 모두 메서드에서 진행한다.
  • Enqueue 할 때 visit을 true로 한다.
• 모든 문제가 DFS로 풀리지는 않는다. BFS가 유리한 문제도 존재한다.
  • https://www.acmicpc.net/problem/7576

BackTracking_DFS (Prunning)

• 완전탐색을 하면 시간초과가 나는 문제가 있다.
• DFS에서 Depth가 조금만 내려가도 재귀의 성질로 인해 엄청난 계산량을 생성한다.
• 그러므로 prunning(=불필요한 경우를 제거)을 통해 Depth를 진행하지 않게 만든다.