백트래킹(Back Tracking)

백트래킹(Backtracking) 알고리즘은 해결책에 대한 후보를 구축해 나가다가, 어느 시점에서든 해당 후보가 문제의 해결책이 될 수 없다고 판단되면, 부분 해결책을 버리고 이전 단계로 돌아가는 (즉, "되돌림"을 수행하는) 알고리즘이다.

설명만으로는 어떤 알고리즘인지 알기 어려우니 밑에 설명을 이어가겠다

백트래킹은 주로 재귀함수(Recursive function)를 통해 만들어지며, 트리를 통해 표현이 가능하다

---

백트래킹을 이용하면 좋은 문제

1. 모든 가능한 해를 나열해야 하는 문제 (예: 순열, 조합)
2. 최적의 해를 찾아야 하는 문제 (예: 미로 찾기, 스도쿠)
3. 제약 조건이 있는 상황에서 가능한 해를 찾아야 하는 문제 (예: N-Queens 문제)

---

위 사진과 같이 트리 형태의 자료로 표현이 가능한 상황에 각 노드를 거쳐 모든 경우의 수를 확인할 경우 경로에 따른 해결책의 확인이 가능하며 해결책을 찾아내는데 불가능한 경로라고 한다면 해당 경로를 해결책에서 제외시키고 지나온 길을 다시 지나 다음 노드부터 탐색한다

예시로 아래와 같은 과정을 거칠 수 있다. 임의로 몇개의 경로는 해결책이 될 수 없음으로 정한 경우를 예시로 포함한다

1Aa -> 해결책이 될 수 없는 경로
1Ab
1Ac
1Ba -> 해결책이 될 수 없는 경로
1Bb
1Bc
1Ca -> 해결책이 될 수 없는 경로
1Cb
1Cc
... ...

이후 특정 조건이 만족되는 모든 경우의 수를 기록한다

---

코드

구성요소

함수의 파라미터

• Index -> 탐색이 시작되는 인덱스
• letter -> 재귀를 통해 호출하며 각 경로를 통한 결과를 저장하는 버퍼

함수 내 요소

• 함수를 멈추기위한 조건을 정의
• 경로를 통해 탐색해야하는 노드의 배열
• 배열을 순회하며 백트래킹 함수를 다시 호출

// index -> 현재 처리할 numbers 배열의 인덱스를 나타냅니다
// letter -> 특정 조건을 만족시키는지 확인하기위해 사용하는 버퍼
// 해당 경우의 경우 letter에 추가적으로 문자열을 더해 조건을 만족시키면 다른 배열에 저장하는 조건
func backTracking(_ index: Int, _ letter: String) {
		// 조건이 들어가는 자리
        if index == numbers.count {
            result.append(letter)
            return
        }
                
        //현재 대상에서 탐색되는 위치
        let num = numbers[index]
        // 현재 대상에서 경로를 통해 이어지는 모든 노드가 저장되는 배열
        guard let c = nums[num] else {return}
        
        // 배열 순회를 통해 각 루트를 따라 이동하여 백트래킹 함수를 재귀적으로 실행
        for i in c {
            backTracking(index + 1, letter + i) 
            //-> 재귀를 통해 데이터를 축적하여 조건을 만족시키기 위해 문자열 i를 추가
        }
    }

---

문제 예시에 대한 코드

Leet code
17. Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

class Solution {
    let nums: [Character: [String]] = [
            "2":["a","b","c"],
            "3":["d","e","f"],
            "4":["g","h","i"],
            "5":["j","k","l"],
            "6":["m","n","o"],
            "7":["p","q","r","s"],
            "8":["t","u","v"],
            "9":["w","x","y","z"]
            ]
    
    var result = [String]()
    var numbers: [Character] = []
    
    func letterCombinations(_ digits: String) -> [String] {
        if digits.isEmpty {
            return []
        }
        
        numbers = Array(digits)
        
        backTracking(0, "")
        
        return result
    }

    func backTracking(_ index: Int, _ letter: String) {
        if index == numbers.count {
            result.append(letter)
            return
        }

        let num = numbers[index]
        
        guard let c = nums[num] else {return}
        
        
        for i in c {
            backTracking(index + 1, letter + i)
        }
    }
}

---

재귀함수가 제일 어렵다;;