[Algorithm] 백트래킹(Backtracking)이란? (feat. 예제포함)

 

안녕하세요 Foma 💻 입니다!

 

오늘은 프로그래머스 N-Queen 문제를 풀면서 해당 문제가 백트래킹 문제라는 것을 알게 되었는데요.

 

그래서 백트래킹이 무엇이고 어떻게 구현해서 사용해야 하는지에 대해 정리해보려고 합니다.

 

바로 시작할게요~

---

백트래킹이란?

 

모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS로 구현했다간 큐의 크기가 . 심지어 속도도 똑같다. 따라서 경우의 수 구하기는 일반적으로 DFS가 편리하다. 대다수의 문제들은DFS를 써도 일단 답은 나온다. - 나무 위키 -

 

즉, DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘 입니다.

 

이렇게 말하면 이해하기 힘드실거에요.

---

홀짝 만들기

 

A,B,C 세 사람이 가지고 있는 숫자를 차례대로 하나씩 줄 세웁니다.

 

단, 조건은 짝수나 홀수가 연속으로 2번 나오면 안됩니다.

 

이 때 만들 수 있는 숫자를 모두 구하시오.

 

(순서는 A-B-C 입니다.)

 

 

A - 1 

B - 4

C-  7

 

홀수나 짝수가 연속되지 않으므로 가능합니다.

 

A - 1

B - 4

C - 8

 

짝수가 연속되므로 가능하지 않습니다.

 

A - 1

B - 4

C - 9

 

홀수나 짝수가 연속되지 않으므로 가능합니다.

 

A - 1

B - 5

 

홀수가  연속되므로 가능하지 않습니다.

 

고로 B의 다음 숫자로 바로 넘어갑니다.

 

이런식으로 조건들을 하나씩 대입해가면서 만약 조건에 맞지 않는다면 그 즉시 중단하고 다음 숫자로 넘어갑니다.

 

그리곤 모든 경우를 탐색해 가능한 모든 숫자 조합을 찾아냅니다.

---

코드 구현

 

A,B,C의 숫자들을 차례로 담아 2차원 배열로 넣어주겠습니다.

 

[[1,2,3],[4,5,6],[7,8,9]]

 

가능한 숫자 조합들을 담을 answer 2차원 배열을 만들어줍니다.

 

var answer:[[Int]] = []

 

 

A,B,C의 숫자들을 담는 numbers,

 

현재 깊이가 어느 정도인지 나타낼 depth,

 

가능한 숫자 조합을 넣을 answer,

 

현재 depth까지 숫자들을 기억할 history를 파라미터로 구현해줍니다.

 

func dfs(numbers:[[Int]],depth:Int,answer:inout [[Int]],history:[Int]) {
...

 

만약 depth가 numbers의 끝까지 왔다면 모든 숫자들이 조건에 맞았다는 의미이므로 answer에 history를 넣어줍니다.

 

if depth == numbers.count {
        answer.append(history)
        return
    }

 

만약 history가 비어있을 경우 가장 첫번째(A)이므로 history에 숫자를 넣어주고 depth를 +1 해준 뒤 재귀해줍니다.

 

if history.isEmpty {
        for n in numbers[depth] {
            var newHistory = history
            newHistory.append(n)
            dfs(numbers: numbers, depth: depth+1, answer: &answer, history: newHistory)
        }

 

만약 history가 비어있지 않다면 현재 depth의 숫자들을를 순회하며 history의 맨 마지막 숫자와 현재 숫자가 홀수나 짝수가

 

연속되지 않는다면 history에 추가해주고 depth를 +1 시켜줍니다.

 

else {
        for n in numbers[depth] {
            //마지막 숫자가 짝수고 n이 홀수라면
            if history.last!%2 == 0 && n%2 != 0 {
                var newHistory = history
                newHistory.append(n)
                dfs(numbers: numbers, depth: depth+1, answer: &answer, history: newHistory)
            }
            //마지막 숫자가 홀수고 n이 짝수라면
            if history.last!%2 != 0 && n%2 == 0 {
                var newHistory = history
                newHistory.append(n)
                dfs(numbers: numbers, depth: depth+1, answer: &answer, history: newHistory)
            }
        }
    }

 

이런식으로 반복하고 모든 탐색이 끝났을 때 answer를 출력해주면 홀수와 짝수가 연속되지 않는 숫자들의 조합이 담겨있는

 

모습을 볼 수 있습니다.

 

func solution(_ numbers:[[Int]]) {
    var answer:[[Int]] = []
    dfs(numbers: numbers, depth: 0, answer: &answer, history: [])
    print(answer)
}

//[[1, 4, 7], [1, 4, 9], [1, 6, 7], [1, 6, 9], [2, 5, 8], [3, 4, 7], [3, 4, 9], [3, 6, 7], [3, 6, 9]]

---

Source Code