[Swift] 백트래킹

백트래킹

모든 경우의 수를 고려하는 알고리즘. 답이될 수 없는 후보는 더이상 탐색하지 않고 다시 돌아가는 알고리즘

 

백트래킹 절차

DFS - 유망한 노드 검토 - 서브트리 이동 - 백트래킹 수행

1. DFS 수행 : 재귀를 호출하면서 DFS를 그대로 수행
2. 유망한 노드 검토 : 유망한 노드면 서브트리로 이동하고, 그렇지 않으면 백트래킹을 수행해야함
3. 서브트리 이동 : 방문한 노드의 하위 노드로 이동하여 다시 재귀를 통해 DFS 수행
4. 백트래킹 수행 : 더이상 유효한 노드라고 생각되지 않으면 상위 노드로 백하여 백트래킹 수행

 

백트래킹 대표 예제

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

var nm = readLine()!.split(separator: " ").map{ Int($0)! }
let N = nm[0]
let M = nm[1]

var stack = [Int]()

private func dfs() {
    if stack.count == M {
        print(stack.map{ String($0) }.joined(separator:" "))
        return
    }

    for i in 1...N {
        if !stack.contains(i) {
            stack.append(i)
            dfs()
            stack.removeLast()
        }

    }
}

dfs()

 

 

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

func dfs(depth: Int, start: Int) {
    // depth 가 반이됐다는 뜻은 이미 한 팀 구성이 완료 됐다는 뜻
    // 그래서 depth = n/2 가 되면, 팀구성못한애들을(false) team2에 넣어줌!!
    if depth == n/2 {
        team1 = 0
        team2 = 0
        for i in 0..<n{
            for j in 0..<n{
                if !visited[i] && !visited[j]{
                    team2 += s[i][j]
                }
                if visited[i] && visited[j] {
                    team1 += s[i][j]
                }
            }
        }
        // 그리고 팀구성이 완료된 애들의 차를 구해서 min값을 계속 갱신시켜주자
        minResult = min(minResult, abs(team1 - team2))
        return
    }
    for i in start..<n {
        if !visited[i] {
            visited[i] = true
            dfs(depth: depth + 1, start: i)
            visited[i] = false
        }
    }
}

 

백트래킹 이해에 도움이 되는 영상

https://www.youtube.com/watch?v=Enz2csssTCs 

---

Ref

https://didu-story.tistory.com/270 

https://didu-story.tistory.com/371

https://www.youtube.com/watch?v=Enz2csssTCs