핵심 요약
- 해를 찾는 도중 해가 아니어서 막힐경우, 되돌아가서 다시 해를 찾아가는 기법
- 시간 복잡도를 감소시킬 수 있는 기법
- 최적화 문제, 결정 문제 등을 풀 때 활용한다.
- 유망성 판단(promising)이 중요하다!
사용처
DFS 등
대표 문제
백준 9663, N-Queen 문제.
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
'알고리즘을 위한 간략 정리 > 그래프 탐색' 카테고리의 다른 글
| [C++] 벨만-포드 알고리즘 (0) | 2023.10.08 |
|---|---|
| [C++] 유니온 파인드(Union-Find) (0) | 2023.10.03 |
| [C++] BFS(Breadth-First Search) (0) | 2023.10.03 |
| [C++] DFS(Depth-First Search) (0) | 2023.10.03 |