[알고리즘] 백트래킹이란? (Swift) (feat.DFS/BFS)

 

🙋🏻‍♀️ 백트래킹이란?

백트래킹은 모든 경우의 수를 전부 고려하는 알고리즘이다. 일종의 탐색 알고리즘으로, DFS, BFS 로 모두 구현 가능하다. 백트래킹은, 답이 될 수 없는 후보는 더이상 탐색하지 않고 다시 돌아가는 알고리즘이다. 모든 경우의 수를 고려하는 브루트포스보다 더 시간을 절약할 수 있다.

 

완전탐색의 대표적인 방법에는 DFS가 있다. 재귀를 이용해서 현재시점에서 계속해서 방문할곳을 탐색하고, 방문한다.

반면, 백트래킹은 비효율적인 경로를 차단하고 목표지점에 도달할 수 있는 가능성이 존재하는 곳만 탐색하기 때문에 일종의 가지치기라고도 부른다. 

 

🙋🏻‍♀️ 백트래킹 절차

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

 

🙋🏻‍♀️ 백트래킹 대표 예제

사실 대표 예제는 백준의 N-Queen 문제이다. 하지만, 난 풀지 않았기에, 내가 푼 풀이를 기반으로 설명해보겠다.

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

[백준] (Swift) 14889번 - 스타트와 링크 (DFS-백트래킹)

 

문제는, 간단하게 설명해서, 주어진 n 이 있는데, n/2 깊이가 되면 dfs를 멈춰야하는 문제였다. (내가 해석한 바로는 이럼)

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
        }
    }
}

이 처럼, func dfs 안에 초반에 if 문으로 depth 의 값 먼저 확인한다. 만약 if 의 조건이 만족하게 된다면, return 하면서 dfs의 한 턴을 끝내게 된다.

---

이처럼 백트래킹은 무언가 특별한 개념은 아니고, DFS/BFS 를 구현할 줄 안다면 충분히 습득 가능한 내용인 것 같다. (난 잘 못했지만  ㅠㅠㅠ) 앞으로 백트래킹에 대한 개념이 나오는 문제는 꼭 맞춰야징!

 

 

📖 Reference

https://velog.io/@mmindoong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9BackTracking

[알고리즘] 백트래킹(BackTracking)