[코딩인터뷰] 백트래킹 Back tracking

https://media.geeksforgeeks.org/wp-content/uploads/N_Queen_Problem.jpg

백트래킹 Back tracking

백트래킹 (Back tracking)은 문제 해결 전략 중 하나로, 가능한 모든 경우의 수를 탐색하는 전략인 브루트 포스(Brute force) 전략에서 특정 조건을 만족하지 못하는 경우의 수들을 탐색 범위에서 제외시키며 탐색하는 전략입니다. 브루트 포스 전략은 모든 경우의 수를 전부 탐색하지만 백트래킹 전략은 특정 조건을 만족하지 못하는 경우의 수를 탐색에서 제외하기 때문에 브루트 포스 전략보다 탐색 효율이 좋습니다.

백트래킹 전략은 재귀적으로 조건을 만족하는지 검토하면서 정답을 완성합니다. 정답을 완성하는 과정 중 조건을 만족하지 못하는 경우의 수와 관련된 경우의 수들을 탐색 범위에서 제외시킵니다. 첫 정답이 완성되면 전 상태로 되돌리고 다른 가능한 경우의 수를 탐색합니다.

전략 기본 순서

백트래킹 전략은 기본적으로 다음과 같은 순서로 동작합니다.

1. 가능한 모든 경우의 수 중 조건을 만족하며 정답이 가능한 첫 데이터를 정답에 추가합니다.
2. 다음 단계 탐색을 시작합니다. 매 탐색마다 탐색 내용을 일단 정답에 추가하고 정답이 조건을 만족하는지 평가합니다.
3. 조건을 만족한다면 다음 단계 탐색을 시작합니다. 만약 정답이 조건을 만족하지 않는다면 마지막으로 추가된 데이터를 정답에서 제거하고 같은 단계의 다른 경우의 수의 탐색을 시작합니다. 만약 현 단계에서의 모든 경우의 수를 이미 탐색했다면 정답의 마지막 데이터를 제거해서 이전 단계로 돌아갑니다.
4. 만약 마지막 단계의 정답을 탐색했고 정답이 조건을 만족했을 경우 현재 정답 리스트를 반환하거나 기록합니다.

요약하자면, 백트래킹 전략은 탐색 단계 별로 조건을 검토하면서 정답을 완성하고, 마지막 정답에서 전 단계로 다시 돌아가 나머지 경우의 수를 탐색하는 과정이 핵심입니다.

전략 적용 조건

따라서 코딩 테스트 문제 중 백트래킹 전략을 적용하기 위해서는 최소한 다음 조건이 만족되어야 합니다.

• 경우의 수가 제한되어 있어야 합니다. 무한한 소수를 찾는 문제는 경우의 수가 제한적이지 않기 때문에 백트래킹 전략을 적용할 수 없습니다
• 이전 탐색과 이후 탐색이 연관이 있어야 합니다. 백트래킹 전략은 정답을 이어붙혀 나가는 방식이기 때문입니다. 배열에서 특정 값이 얼마나 존재하는지를 카운팅하는 문제는 이전 탐색과 이후 탐색이 연관이 없습니다. 따라서 정답을 단계 별로 완성할 수 없으며, 모든 경우의 수를 탐색해야만 정답을 알 수 있기 때문에 경우의 수를 조건에 따라 줄이는 백트래킹 전략을 적용할 수 없습니다.

예시

이해를 돕기 위해 다음 문제를 백트래킹 전략으로 푸는 과정을 소개하겠습니다.

---

[1, 2, 3, 4, 5] 중 3 개를 선택하여 만든 배열 중 합이 6 이하인 배열 모두를 찾아라.

1 배열 A 를 [0, 0, 0] 으로 초기화합니다. 배열 A는 선택된 숫자들이 조건을 만족하는지 파악하기 위한 배열입니다.
2 배열 V 를 [[1,2,3,4,5], [1,2,3,4,5], [1,2,3,4,5]]로 초기화합니다. 배열 V는 무한히 방문하지 않도록 하기 위한 배열입니다.

배열 A [0, 0, 0]
배열 V [[1,2,3,4,5], [1,2,3,4,5], [1,2,3,4,5]]

3 배열 V0 중 '2' 를 선택해 배열 A0 에 넣고 배열 V0 에서 '2'를 제거합니다. 조건을 만족하는 검토하기 전에 정답이 가능한 숫자를 추가합니다.

배열 A [2, 0, 0]
배열 V [[1,3,4,5], [1,2,3,4,5], [1,2,3,4,5]]

4 배열 A [2, 0, 0]는 조건 '합이 6 이하' 를 만족하므로, 배열 V1 중 '5' 을 선택하여 배열 A1 에 넣고 배열 V1 에서 '5'을 제거합니다.

A배열 [2, 5, 0]
V배열 [[1,3,4,5], [1,2,3,4], [1,2,3,4,5]]

5 배열 A [2, 5, 0]은 조건 '합이 6 이하' 를 만족하지 못하므로, 배열 A1 위치의 숫자를 제거합니다.

A배열 [2, 0, 0]
V배열 [[1,3,4,5], [1,2,3,4], [1,2,3,4,5]]

6 다시 배열 V1 중 '3'를 선택하여 배열 A1 에 넣고 배열 V1 에서 '3'을 제거합니다.

A배열 [2, 3, 0]
V배열 [[1,3,4,5], [1,2,4], [1,2,3,4,5]]

7 배열 A [2, 3, 0]는 조건 '합이 6 이하' 를 만족하므로, 배열 V2 중 '1' 을 선택하여 배열 A2 에 넣고 배열 V2 에서 '1'을 제거합니다.

A배열 [2, 3, 1]
V배열 [[1,3,4,5], [1,2,4], [2,3,4,5]]

8 배열 A [2, 3, 1]는 조건 '합이 6 이하' 를 만족하며 모든 배열을 채웠으니 결과에 추가합니다. 그리고 배열 A2 를 제거합니다. 백트래킹 전략의 핵심인 부분입니다. 완성한 정답을 기록한 뒤에 정답을 이전 상태로 되돌려 다른 경우의 수를 탐색합니다.

A배열 [2, 3, 0]
V배열 [[1,3,4,5], [1,2,4], [2,3,4,5]]

9 배열 V2 중 '2' 을 선택하여 배열 A2 에 넣고 배열 V2 에서 '2'을 제거합니다.

A배열 [2, 3, 2]
V배열 [[1,3,4,5], [1,2,4], [3,4,5]]

10 배열 A [2, 3, 2]은 조건 '합이 6 이하' 를 만족하지 못하므로, 배열 A2 위치의 숫자를 제거합니다.

반복합니다...

---

위와 같이 풀면 문제의 정답을 맞출 수는 없지만 백트래킹 전략의 핵심은 파악할 수 있습니다. 백트래킹 전략은 매 단계 별로 조건을 검토하면서 정답을 완성하고, 조건을 만족하지 못하는 경우의 수를 탐색에서 제외하며, 마지막 정답에서 전 단계로 다시 돌아가 나머지 경우의 수를 탐색하는 과정을 거쳐 정답을 찾아내는 전략입니다.

관련 백준 문제

10819 차이를 최대로
9663 n-queen - 대표 백트래킹 전략 문제
14889 스타트와 링크
2661 좋은수열
14888 연산자끼워넣기
15684 사다리조작 - 삼성 SW 역량 테스트 기출
15686 치킨배달 - 삼성 SW 역량 테스트 기출
1987 알파벳
2580 스도쿠