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

알고리즘

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

위시리 2024. 9. 24. 14:18

백트래킹이란?

어떤 가능성이 없는 곳에서 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘

즉, 불필요한 경우를 배제하며 원하는 해답에 도달할 때까지 탐색하는 전략

백트래킹 알고리즘은 문제마다 효율이 달라지므로 시간 복잡도를 특정하여 정의하기 어렵다. 하지만 백트래킹을 통해 해가 될 가능성이 없는 탐색 대상을 배제할 수 있으므로 탐색 효율이 모든 경우를 확인하는 완전 탐색보다 효율적이다.

어떻게 해가 될 가능성을 판단하는가?

유망 함수를 정의하여 가능성을 판단

유효한 해의 집합 정의
위 단계에서 정의한 집합을 그래프로 표현
유망 함수 정의 : 특정 조건을 정의
백트래킹 알고리즘을 활용하여 해 찾기

동작 예시 (합이 6을 넘는 경우 알아보기) : https://goldenrabbit.co.kr/2023/12/29/%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9%EC%9E%90-%EB%90%98%EA%B8%B0-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-1-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9%EA%B3%BC-%EB%B0%B1/

[코딩 테스트 합격자 되기] 백트래킹– 1. 백트래킹과 백트래킹 알고리즘 개념 - 골든래빗

백트래킹의 개념을 이해하고, 전체 탐색(brute force, 브루트 포스)과 차이점을 설명할 수 있습니다. 유망 함수를 활용해서 더 효율적인 트리 탐색 알고리즘을 구현할 수 있습니다.

goldenrabbit.co.kr

백트래킹은 DFS를 기반으로 한다. 백트래킹은 기본적으로 모든 경우의 수를 탐색하는 브루트 포스(Brute Force) 전략을 취하지만, 처리속도를 향상시키기 위해 가지치기(Pruning)을 한다. 나무에서 불필요한 가지를 제거하듯이 백트래킹에서 가지치기를 잘 할 수록 불필요한 경우가 제거되어 처리속도가 향상된다.

DFS와 백트래킹 차이점

DFS : 해를 찾을 때 까지 가능한 '모든 경로'를 추적
백트래킹 : 현재 방문한 노드가 해가 될 가능성이 없으면 더 이상 해당 경로를 탐색하지 않고(가지치기) 되돌아와서 다음 경로 탐색

이때 찾는 경로가 여러개라면,

DFS : 모든 노드를 방문해서 경로 하나를 찾으면 다른 가능한 경로는 더 찾지 않고 종료
백트래킹 : 가능한 모든 경로들을 모두 찾음

백트래킹은 "같은 노드를 거치는 다른 경로들도 모두 찾아야 하기" 때문에, "이전에 방문한 노드를 다음 탐색에서 또 방문할 수 있다." 라는 DFS와의 차별점을 가진다. 이를 위해서는 한 노드를 방문 처리하고 이후 탐색을 진행하고 돌아와서, 그 노드를 방문하지 않은 것으로 원상복구해야된다.

순열을 예시로 볼 때, 1 2 o o 의 경우를 파악 후 1 3 o o 에 대한 탐색을 할 때