BFS(Breadth-First Search)
- 계층/깊이 별로 순환탐색하는 방법
- 대표적 예) 친구 찾기 → 큐 이용
- 깊이마다 노드들을 우선순위에 따라 차례대로 넣고 큐에서 순서대로 꺼내어 순환을 하는 형태
- 자식 노드의 자식 노드를 탐색할 때, 메모리 소모가 크다. 트리의 깊이마다 노드들이 많고 트리가 넓을 때 등은 보통 사용하지 않는다.(최단경로 찾기나 찾는 노드가 인접할 경우 효과적)
DFS(Depth-First Search)
- 연결되어 있는 노드들의 우선순위에 따라 최대한 깊게 들어가는 방법
- 대표적 예) 전략 게임에서 하나의 수에 잇따른 가능성들을 파고 들때 사용 → 스택 이용 like 재귀함수
- 찾는 노드의 depth가 깊을 수록 빠르고, 메모리 소모가 적다.
- 깊이의 끝이 없거나 너무 깊이 들어가는 경우는 사용을 지양해야한다.(탈출불가)
한눈에 보는 DFS와 BFS
Backtracking(백트래킹)
- 완전탐색 : 여러 개의 solution을 가진 문제에서, 모든 solution을 탐색하는 전략
- 대표적 예 : 재귀 호출 or 스택을 통한 DFS
백트래킹의 원리
- 어떤 노드의 유망성을 점검 후,
- 유망하지 않으면 배제시킨다. = 가지치기
- 해당 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. → 풀이시간 단축
N-Queens 구현과 백트래킹
- 헬퍼함수를 어떤 식으로 이용하여 '특정조건(유망성)'을 따질 것인가
- n개만큼의 rooks 혹은 queens가 존재하는가?
- 충돌이 존재하지 않는가?
- 조건에 부합하지 않는 경우는 어떤 식으로 넘어갈 것인가
- 위 조건을 충족하지 않는다면, 다음 row 로 넘어가서 탐색을 진행하자.
유망성과 가지치기
- 유망성(Promising) : 가망이 있는가 없는가를 따지는 기준
- 가지치기(Pruning) : 유망성을 따져보고, 유망하지 않는 경우의 수는 배제하는 것으로 간단히 말하면 '불필요한 부분을 쳐낸다'로 보면 된다.
Backtracking & N-Queens
[알고리즘] 되추적(Backtracking)을 알아보자.
[알고리즘] Backtracking 이해하기
알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제
차곡차곡 쌓아가는 나의 개발 기록