백트래킹(BackTracking) 알고리즘

백트래킹 알고리즘이란?

---

백트래킹(Back Tracking) 알고리즘은 탐색 알고리즘 중 하나로 

가능성이 없는 곳은 되돌아가고 가능성이 있는 곳은 탐색하는 알고리즘이다.

 

집에서 나왔는데 지갑을 두고 나와 다시 돌아간다고 한다면

우선 아파트로 갈것 이다.

그런 다음 우리는 자연스럽게 내 호수에 해당하는 집으로 향할 것이다.

지갑은 내 집, 내 방에 있기 때문에 굳이 다른 집을 들어가 방을 찾지 않아도 된다.

이것이 바로 백트래킹의 원리이다. 가능성이 없는 건 하지 않는다. 

 

백트래킹 알고리즘은 일반적으로 재귀를 통해 구현되며 모든 경우의 수를 시도해보는 완전탐색 기법 중 하나다.

하지만 가능한 해가 아닌 경우를 미리 배제함으로써 탐색 공간을 줄이고, 문제를 효율적으로 해결할 수 있도록 한다.

따라서 너비 우선 탐색이나 깊이 우선 탐색에 비해 효율이 좋다.

 

 

백트래킹 알고리즘 주요 절차

---

1. 유효한 해의 집합을 정의한다.

(선택) 정의한 집합을 문제에 따라 그래프로 표현할 수도 있다.

 

2. 해당 해가 유망한지 아닌지를 판단할 수 있는 유망함수를 정의한다.

 

3. 유망함수를 통해 해당 해가 유망한 해인지를 판단해 유망하다면 탐색하고 유망하지 않다면 탐색하지 않는다. 

 

4. 현재 단계에서 가능한 모든 해를 시도하며 재귀적으로 반복한다.

예시: 합이 6을 넘는 경우

[1, 2, 3, 4] 중 2개의 숫자를 뽑아서 합이 6을 초과하는 경우를 알아내는 과정을 백트래킹 알고리즘을 통해 풀어보자.

뽑는 순서가 다르면 다른 경우의 수로 간주한다.

 

1. 유효한 해의 집합을 정의한다.

[1, 2], [1, 3], [1, 4],  [2, 1], [2, 3], [2, 4]

[3, 1], [3, 2], [3, 4],  [4, 1], [4, 2], [4, 3]

(선택) 정의한 집합을 그래프로 표현한다.

 

2. 해당 해가 유망한지 아닌지를 판단할 수 있는 유망함수를 정의한다.

두 숫자 중 하나라도 3미만이면 6을 초과할 수 없기 때문에 '첫번째 숫자가 3미만인 경우 백트래킹 한다.'를 유망함수로 정의한다.

 

3. 유망함수를 통해 해당 해가 유망한 해인지를 판단해 유망하다면 탐색하고 유망하지 않다면 탐색하지 않는다. 

1과 2의 경우 3미만이므로 백트래킹한다.

 

3과 4는 유망하기 때문에 탐색한다.

정답은 [3, 4], [4, 3]이 된다.

 

이처럼 백트래킹을 이용하면 효율적으로 탐색을 할 수 있다.

 

 

해당 포스트는 『코딩 테스트 합격자 되기 - 자바편』을 참고하여 작성되었습니다.