[알고리즘] 백트래킹 유형 정리

백트래킹 문제 풀때 유형별 풀이가 너무 헷갈려서 정리하는 포스팅

 

1. 단순 순열(순서가 다르면 겹치는게 있어도 다른 케이스로 간주, ab != ba)

- 모든 케이스를 다 돌기는 해야하는데, 현재 루프에서 이미 방문한 노드는 제외해야할 때

 

N과 M (1)

스도쿠

- 1부터 9를 중복없이 채운다는 전제하에 1 9 와 9 1은 다른 케이스일 수 밖에 없음. 여기에 행/열/사각형에 중복이 없는지에 대한 조건 추가하는 응용만 제외하면 아래 원리와 동일

 

알고리즘 틀

// 구현해놓은 Permutation 연습
func permute(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
    var result = [[Int]]()
    var visited = [Bool](repeating: false, count: nums.count)
    
    func permutation(_ nowPermute: [Int]) {
        if nowPermute.count == targetNum {
            result.append(nowPermute)
            return
        }
        for i in 0..<nums.count {
            if visited[i] == false {
                visited[i] = true
                permutation(nowPermute + [nums[i]])
                visited[i] = false
            }
        }
    }
    permutation([])
    
    return result
}

 

2. 단순 조합(겹치는 순간 같은 케이스로 간주, ab = ba)

N과 M(2)

치킨 배달

부분수열의 합

다이어트

암호만들기

- 뽑는 수에 중복이 없다는 것이 공통적

 

알고리즘 틀

func combi(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
    var result = [[Int]]()

    func combination(_ index: Int, _ nowCombi: [Int]) {
        if nowCombi.count == targetNum {
            result.append(nowCombi)
            return
        }
        for i in index..<nums.count {
            combination(i + 1, nowCombi + [nums[i]])
        }
    }

    combination(0, [])

    return result
}