[알고리즘] Backtracking (백 트래킹)

Backtracking (백 트래킹)

• 모든 경우의 수를 전부 고려하는 알고리즘이다.

• 즉, 조합 알고리즘 문제에 대해 어떤 조건을 만족할 때 모든 가능한 해를 나열한 것이다.

• 일종의 트리 탐색 알고리즘으로 DFS, BFS 등의 방식을 사용한다.

  • DFS

    • 모든 경우의 수를 고려해야 하는 문제일 때 주로 사용한다.

    • 하지만 트리의 깊이가 무한대가 될 때는 절대 사용하면 안된다. (무한루프에 빠짐) -> 이 때, 중복검사를 따로 해야 함

  • BFS 

    • 최단거리를 구할 때 주로 사용한다.

 

Backtraking의 대표적인 예제로 N-Queen이 있다.